Bidirectional Search in a String with Wavelet Trees
Bidirectional Search in a String with Wavelet Trees
复制标题
使用小波树在字符串中进行双向搜索
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Simon Gog
中科院分区：
文献类型：
--
作者：
T. Schnattinger;Enno Ohlebusch;Simon Gog
寻找编码microRNA（miRNAs）的基因是基因组分析中的一项重要任务。由于miRNA的二级结构（而不是序列）是高度保守的，因此可以通过在基因组DNA序列中找到与结构匹配的区域来确定编码它的基因。已知的是，对于该任务，在DNA序列上使用双向搜索的算法优于基于单向搜索的算法。然而，支持双向搜索的数据结构（词缀树和词缀数组）相当复杂，并且占用大量空间。在这里，我们提出了一种新的数据结构称为双向小波索引，支持双向搜索，空间少得多。利用这种数据结构，可以在大型基因组中搜索RNA二级结构模式，例如人类基因组。
Searching for genes encoding microRNAs (miRNAs) is an important task in genome analysis. Because the secondary structure of miRNA (but not the sequence) is highly conserved, the genes encoding it can be determined by finding regions in a genomic DNA sequence that match the structure. It is known that algorithms using a bidirectional search on the DNA sequence for this task outperform algorithms based on unidirectional search. The data structures supporting a bidirectional search (affix trees and affix arrays), however, are rather complex and suffer from their large space consumption. Here, we present a new data structure called bidirectional wavelet index that supports bidirectional search with much less space. With this data structure, it is possible to search for RNA secondary structural patterns in large genomes, for example the human genome.