Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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 agreements between two bucket orders of n elements, their Longest Common Subsequence (LCS), providing an efficient solution to highlight discrepancies between two genetic maps. The LCS of two maps, being the largest set of their collinear markers, is used as a building block to compute pairwise map congruence, to visually emphasize maker collinearity and in some scaffolding methods relying on genetic maps to improve genome assembly. As the LCS computation is a key subroutine of all these genetic map related tools, replacing the current LCS subroutine of those methods by ours - to do the exact same work but faster-could significantly speed up those methods without changing their accuracy. To ease such transition we provide all required algorithmic details in this self contained paper as well as an R package implementing them, named LCSLCIS, which is freely available at:
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
Contributeur : Sèverine Bérard <>
Soumis le : mardi 26 mai 2020 - 03:10:28
Dernière modification le : mercredi 14 octobre 2020 - 03:58:41


Fichiers éditeurs autorisés sur une archive ouverte


Distributed under a Creative Commons Paternité 4.0 International License



Lisa de Mattéo, Yan Holtz, Vincent Ranwez, Sèverine Bérard. Efficient algorithms for Longest Common Subsequence of two bucket orders to speed up pairwise genetic map comparison. PLoS ONE, Public Library of Science, 2018, 13 (12), pp.e0208838. ⟨10.1371/journal.pone.0208838⟩. ⟨hal-02134202⟩



Consultations de la notice


Téléchargements de fichiers