title: 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. 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 is the optimal output size.
authors.affiliation: Department of Informatics, King's College London, , London WC2R 2LS, UK.
authors.forename: Maxime
authors.initials: M
authors.lastname: Crochemore
authors.forename: Alessio
authors.initials: A
authors.lastname: Langiu
authors.forename: M Sohel
authors.initials: MS
authors.lastname: Rahman
keywords: algorithms; genome sequence; indexing; mapping reads; mismatch; pattern matching
references.citation: Nat Genet. 2002 Apr;30(4):377-84
references.pmid: 11925564
references.citation: J Biol Chem. 2003 Feb 28;278(9):6748-54
references.pmid: 12493737
references.citation: Genome Biol. 2011 Nov 08;12(11):R112
references.pmid: 22067484