Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2010

Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps

Résumé

Chaining fragments is a crucial step in genome alignment. Existing chaining algorithms compute a maximum weighted chain with no overlaps allowed between adjacent fragments. In practice, using local alignments as fragments, instead of MEMs, generates frequent overlaps between fragments, due to combinatorial reasons and biological factors, i.e. variable tandem repeat structures that differ in number of copies between genomic sequences. In this paper, in order to raise this limitation, we formulate a novel definition of a chain, allowing overlaps proportional to the fragments lengths, and exhibit an efficient algorithm for computing such a maximum weighted chain. We tested our algorithm on a dataset composed of 694 genome couples and accounted for significant improvements in terms of coverage, while keeping the running times below reasonable limits.
Fichier principal
Vignette du fichier
Uricaru-etal-chaining-overlap-rr-2010-1.pdf (254.97 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00527915 , version 1 (20-10-2010)

Identifiants

Citer

Raluca Uricaru, Alban Mancheron, Eric Rivals. Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps. RECOMB-CG: Comparative Genomics, Oct 2010, Ottawa, Canada. pp.161-172, ⟨10.1007/978-3-642-16181-0_14⟩. ⟨lirmm-00527915⟩
153 Consultations
703 Téléchargements

Altmetric

Partager

More