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

ABSTRACT: Genetic maps order genetic markers along chromosomes. They are, for instance, extensively used in marker-assisted selection to accelerate breeding programs. Even for the same species, people often have to deal with several alternative maps obtained using different ordering methods or different datasets, e.g. resulting from different segregating populations. Having efficient tools to identify the consistency and discrepancy of alternative maps is thus essential to facilitate genetic map comparisons. We propose to encode genetic maps by bucket order, a kind of order, which takes into account the blurred parts of the marker order while being an efficient data structure to achieve low complexity algorithms. The main result of this paper is an O(n log(n)) procedure to identify the largest agree

SUBMITTER: De Matteo L 

PROVIDER: S-EPMC6320017 | biostudies-literature | 2018

REPOSITORIES: biostudies-literature