Efficient algorithms for Longest Common Subsequence of two bucket orders to speed up pairwise genetic map comparison

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Genetic maps are essential for marker-assisted selection in breeding.
• Multiple genetic maps often exist for the same species due to varying data and methods.
• Efficient tools are needed for comparing genetic maps and identifying inconsistencies.

Purpose of the Study:

• To develop an efficient algorithm for comparing genetic maps.
• To provide a method for identifying consistency and discrepancies between alternative genetic maps.
• To facilitate the use of genetic map comparisons in breeding and genome assembly.

Main Methods:

• Encoding genetic maps using bucket orders, a data structure handling blurred marker order.
• Developing an O(n log n) procedure to compute the Longest Common Subsequence (LCS) of two bucket orders.
• Implementing the algorithm in an R package (LCSLCIS) for accessibility.

Main Results:

• An efficient O(n log n) algorithm for finding the LCS between two genetic maps represented as bucket orders.
• The LCS identifies the largest set of collinear markers, highlighting map agreements.
• The method provides a faster alternative for existing genetic map comparison tools.

Conclusions:

• The proposed LCS algorithm offers a significant speed-up for genetic map comparison without compromising accuracy.
• This facilitates more efficient marker-assisted selection and genome assembly scaffolding.
• The LCSLCIS R package enables easy adoption of this improved computational method.