Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-14355-7_19
Title: Indexing similar DNA sequences
Authors: Huang, S.
Lam, T.W.
Sung, W.K. 
Tam, S.L.
Yiu, S.M.
Issue Date: 2010
Source: Huang, S.,Lam, T.W.,Sung, W.K.,Tam, S.L.,Yiu, S.M. (2010). Indexing similar DNA sequences. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6124 LNCS : 180-190. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-14355-7_19
Abstract: To study the genetic variations of a species, one basic operation is to search for occurrences of patterns in a large number of very similar genomic sequences. To build an indexing data structure on the concatenation of all sequences may require a lot of memory. In this paper, we propose a new scheme to index highly similar sequences by taking advantage of the similarity among the sequences. To store r sequences with k common segments, our index requires only O(n + N logN) bits of memory, where n is the total length of the common segments and N is the total length of the distinct regions in all texts. The total length of all sequences is rn + N, and any scheme to store these sequences requires Ω(n + N) bits. Searching for a pattern P of length m takes O(m+mlogN +mlog(rk)psc(P)+occ log n), where psc(P) is the number of prefixes of P that appear as a suffix of some common segments and occ is the number of occurrences of P in all sequences. In practice, rk ≤ N, and psc(P) is usually a small constant. We have implemented our solution1 and evaluated our solution using real DNA sequences. The experiments show that the memory requirement of our solution is much less than that required by BWT built on the concatenation of all sequences. When compared to the other existing solution (RLCSA), we use less memory with faster searching time. © Springer-Verlag Berlin Heidelberg 2010.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40901
ISBN: 3642143547
ISSN: 03029743
DOI: 10.1007/978-3-642-14355-7_19
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

23
checked on Dec 13, 2017

Page view(s)

45
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.