A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays |
| |
Authors: | Wing-Kai Hon Tak-Wah Lam Kunihiko Sadakane Wing-Kin Sung Siu-Ming Yiu |
| |
Affiliation: | (1) Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong;(2) Department of Computer Science and Communication Engineering, Kyushu University, Kyushu, Japan;(3) School of Computing, National University of Singapore, Singapore, Singapore |
| |
Abstract: | With the first human DNA being decoded into a sequence of about 2.8 billion characters, much biological research has been
centered on analyzing this sequence. Theoretically speaking, it is now feasible to accommodate an index for human DNA in the
main memory so that any pattern can be located efficiently. This is due to the recent breakthrough on compressed suffix arrays,
which reduces the space requirement from O(n log n) bits to O(n) bits. However, constructing compressed suffix arrays is still
not an easy task because we still have to compute suffix arrays first and need a working memory of O(n log n) bits (i.e.,
more than 13 gigabytes for human DNA). This paper initiates the study of constructing compressed suffix arrays directly from
the text. The main contribution is a construction algorithm that uses only O(n) bits of working memory, and the time complexity
is O(n log n). Our construction algorithm is also time and space efficient for texts with large alphabets such as Chinese
or Japanese. Precisely, when the alphabet size is |Σ|, the working space is O(n log |Σ|) bits, and the time complexity remains
O(n log n), which is independent of |Σ|. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|