Indexing a sequence for mapping reads with a single mismatch

Maxime Crochemore; Alessio Langiu; M. Sohel Rahman

Indexing a sequence for mapping reads with a single mismatch

Maxime Crochemore ^{1, 2} Alessio Langiu ^{3, 1} M. Sohel Rahman ¹

1 Department of Computer Science [London]

2 LIGM - Laboratoire d'Informatique Gaspard-Monge

3 DEIM - Dipartimento di Energia, ingegneria dell'Informazione e modelli Matematici [Palermo]

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.

Keywords : mismatch pattern matching algorithms genome sequence indexing mapping reads

Document type :

Journal articles

Domain :

Computer Science [cs] / Bioinformatics [q-bio.QM]

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

Cited literature [54 references] Display Hide Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01375933
Contributor : Admin Upem <>
Submitted on : Monday, October 3, 2016 - 6:38:16 PM
Last modification on : Tuesday, October 30, 2018 - 5:04:09 PM
Long-term archiving on : Friday, February 3, 2017 - 2:01:23 PM

CrochemoreLangiuRahman2014.pdf

Files produced by the author(s)

Indexing a sequence for mapping reads with a single mismatch

File

Identifiers

Collections

Citation

Export

Metrics

291

169

Contact

Indexing a sequence for mapping reads with a single mismatch

File

Identifiers

Collections

Citation

Export

Share

Metrics

291

169

Contact