Constructing suffix tree for gigabyte sequences with megabyte memory
Constructing suffix tree for gigabyte sequences with megabyte memory
复制标题
DOI：
10.1109/tkde.2005.3
复制
发表时间：
2005-01-01
影响因子：
8.9
通讯作者：
Lu, HJ
中科院分区：
文献类型：
--
作者：
Cheung, CF;Yu, JX;Lu, HJ
哺乳动物基因组的大小通常为30亿碱基对（gibabase pairs）。最大的公共DNA数据库——美国国家生物技术信息中心（NCBI，网址为http://www.ncbi.nlm.nih.gov）包含超过200亿碱基对。后缀树被广泛认为是一种数据结构，当它能够存于主存时，可有效地支持精确/近似序列匹配查询以及重复结构查找。但是，由于所谓的内存瓶颈问题，使用后缀树处理长DNA序列已被证明是困难的。最节省空间的主存后缀树构建算法需要9小时和45GB内存空间来为人类基因组建立索引[19]。在本文中，我们表明长DNA序列的后缀树可以使用有限的小主存空间在磁盘上高效构建，因此，所有基于后缀树的现有算法都可用于处理无法在主存中容纳的长DNA序列。我们采用两阶段策略在磁盘上构建后缀树：1）构建一个没有后缀链接的基于磁盘的后缀树；2）如果需要，在磁盘上构建的后缀树基础上重建后缀链接。我们提出了一种新的基于磁盘的后缀树构建算法，称为DynaCluster，它在CPU成本方面表现出O(n log n)的实验行为，在I/O成本方面表现出线性。DynaCluster仅需16MB主存即可构建超过2亿碱基对的DNA序列，并且在构建成本和查询处理成本方面都显著优于使用预分区技术的现有基于磁盘的后缀树构建算法。我们进行了广泛的性能研究，并在本文中报告了我们的研究结果。
Mammalian genomes are typically 3Gbps (gibabase pairs) in size. The largest public database NCBI (National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov)) of DNA contains more than 20 Gbps. Suffix trees are widely acknowledged as a data structure to support exact/approximate sequence matching queries as well as repetitive structure finding efficiently when they can reside in main memory. But, it has been shown as difficult to handle long DNA sequences using suffix trees due to the so-called memory bottleneck problems. The most space efficient main-memory suffix tree construction algorithm takes nine hours and 45 GB memory space to index the human genome [ 19]. In this paper, we show that suffix trees for long DNA sequences can be efficiently constructed on disk using small bounded main memory space and, therefore, all existing algorithms based on suffix trees can be used to handle long DNA sequences that cannot be held in main memory. We adopt a two-phase strategy to construct a suffix tree on disk: 1) to construct a diskbase suffix-tree without suffix links and 2) rebuild suffix links upon the suffix-tree being constructed on disk, if needed. We propose a new disk-based suffix tree construction algorithm, called DynaCluster, which shows O(n log n) experimental behavior regarding CPU cost and linearity for I/O cost. DynaCluster needs 16 MB main memory only to construct more than 200 Mbps DNA sequences and significantly outperforms the existing disk-based suffix-tree construction algorithms using prepartitioning techniques in terms of both construction cost and query processing cost. We conducted extensive performance studies and report our findings in this paper.