Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-22685-4_44
Title: Compressed directed acyclic word graph with application in local alignment
Authors: Hoang, D.H.
Kin, S.W. 
Issue Date: 2011
Source: Hoang, D.H.,Kin, S.W. (2011). Compressed directed acyclic word graph with application in local alignment. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6842 LNCS : 503-518. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-22685-4_44
Abstract: Suffix tree, suffix array, and directed acyclic word graph (DAWG) are data-structures for indexing a text. Although they enable efficient pattern matching, their data-structures require O(n logn) bits, which make them impractical to index long text like human genome. Recently, the development of compressed data-structures allow us to simulate suffix tree and suffix array using O(n) bits. However, there is still no O(n)-bit data-structure for DAWG with full functionality. This work introduces an O(n)-bit data-structure for simulating DAWG. Besides, we also propose an application of DAWG to improve the time complexity for the local alignment problem. In this application, the previously proposed solutions using BWT (a version of compressed suffix tree) run in O(n 2 m) worst case time and O(n m 0.628) average case time where n and m are the lengths of the database and the query, respectively. Using compressed DAWG proposed in this paper, the problem can be solved in O(n m) worst case time and the same average case time. © 2011 Springer-Verlag.
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/41297
ISBN: 9783642226847
ISSN: 03029743
DOI: 10.1007/978-3-642-22685-4_44
Appears in Collections:Staff Publications

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

Page view(s)

63
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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