Indexing sequences for mapping reads with a single mismatch - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences (1934–1990) Année : 2014

Indexing sequences for mapping reads with a single mismatch

Résumé

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 sequences 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 New 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 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 < epsilon < 1 and K is the optimal output size.
Fichier principal
Vignette du fichier
1-mismatch_v2.pdf (176.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01806291 , version 1 (08-06-2018)

Identifiants

  • HAL Id : hal-01806291 , version 1

Citer

Maxime Crochemore, Alessio Langiu, M Sohel. Indexing sequences for mapping reads with a single mismatch. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences (1934–1990), 2014, 372 (2016), pp.1-18. ⟨hal-01806291⟩
37 Consultations
109 Téléchargements

Partager

Gmail Facebook X LinkedIn More