Efficient algorithms for Longest Common Subsequence of two bucket orders to speed up pairwise genetic map comparison - Université de Montpellier Accéder directement au contenu
Article Dans Une Revue PLoS ONE Année : 2018

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

Résumé

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: https://github.com/holtzy/LCSLCIS.
Fichier principal
Vignette du fichier
Publis18-agap-035_matteo_efficient_1.pdf (1.85 Mo) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02134202 , version 1 (26-05-2020)

Licence

Paternité

Identifiants

Citer

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, 2018, 13 (12), pp.e0208838. ⟨10.1371/journal.pone.0208838⟩. ⟨hal-02134202⟩
70 Consultations
43 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More