Indexing a sequence for mapping reads with a single mismatch

Abstract : Mapping reads against a genome sequence is an interesting and useful problem in Computational Molecular Biology and Bioinformatics. In this paper, we focus on the problem of indexing a sequence for mapping reads with a single mismatch. We first focus on a simpler problem where the length of the pattern is given beforehand during the data structure construction. This version of the problem is interesting in its own right in the context of the Next Generation Sequencing (NGS). In the sequel we show how to solve the more general problem. In both cases, our algorithm can construct an efficient data structure in O(n log^(1+ε)n) time and space and can answer subsequent queries in O(m log log n + K) time. Here, n is the length of the sequence, m is the length of the read, 0 < ε < 1 and K is the optimal output size.
Type de document :
Article dans une revue
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Royal Society, The, 2014, 2 (20130167), pp.1-18. 〈10.1098/rsta.2013.0167〉
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-01375933
Contributeur : Admin Upem <>
Soumis le : lundi 3 octobre 2016 - 18:38:16
Dernière modification le : mardi 30 octobre 2018 - 17:04:09
Document(s) archivé(s) le : vendredi 3 février 2017 - 14:01:23

Fichier

CrochemoreLangiuRahman2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Maxime Crochemore, Alessio Langiu, M. Sohel Rahman. Indexing a sequence for mapping reads with a single mismatch. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Royal Society, The, 2014, 2 (20130167), pp.1-18. 〈10.1098/rsta.2013.0167〉. 〈hal-01375933〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

58