Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps

Raluca Uricaru 1 Alban Mancheron 1 Eric Rivals 1, *
* Auteur correspondant
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
Eric Tannier. RECOMB'10: Comparative Genomics, Oct 2010, Ottawa, Canada. Springer-Verlag, 6398 (6398), pp.161-172, 2010, LNCS. 〈http://recombcg.uottawa.ca/recombcg2010/〉. 〈10.1007/978-3-642-16181-0_14〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00527915
Contributeur : Eric Rivals <>
Soumis le : mercredi 20 octobre 2010 - 18:40:23
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 11:46:44

Fichier

Uricaru-etal-chaining-overlap-...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Raluca Uricaru, Alban Mancheron, Eric Rivals. Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps. Eric Tannier. RECOMB'10: Comparative Genomics, Oct 2010, Ottawa, Canada. Springer-Verlag, 6398 (6398), pp.161-172, 2010, LNCS. 〈http://recombcg.uottawa.ca/recombcg2010/〉. 〈10.1007/978-3-642-16181-0_14〉. 〈lirmm-00527915〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

277