Computing the Burrows-Wheeler transform of a string and its reverse in parallel
Computing the Burrows-Wheeler transform of a string and its reverse in parallel
复制标题
并行计算字符串的 Burrows-Wheeler 变换及其逆变换
DOI：
10.1016/j.jda.2013.06.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Abouelhoda
中科院分区：
文献类型：
--
作者：
E. Ohlebusch;T. Beller;M. Abouelhoda
这篇文章的贡献是双重的。首先，我们提供了新的理论见解之间的关系字符串和它的逆：如果一个字符串的Burrows-Wheeler变换（BWT）已计算通过排序其后缀，然后BWT，后缀数组，和最长的公共前缀数组的反向字符串可以从它派生没有后缀排序。此外，我们证明了一个字符串的最长公共前缀数组和它的逆是彼此的排列。其次，我们提供了一个并行算法，给定的BWT的字符串，计算BWT的反向速度比所有已知的（并行）后缀排序算法。一些生物信息学应用将从中受益。
The contribution of this article is twofold. First, we provide new theoretical insights into the relationship between a string and its reverse: If the Burrows–Wheeler transform (BWT) of a string has been computed by sorting its suffixes, then the BWT, the suffix array, and the longest common prefix array of the reverse string can be derived from it without suffix sorting. Furthermore, we show that the longest common prefix arrays of a string and its reverse are permutations of each other. Second, we provide a parallel algorithm that, given the BWT of a string, computes the BWT of its reverse much faster than all known (parallel) suffix sorting algorithms. Some bioinformatics applications will benefit from this.
登录
查看更多内容
计算字符串的 Burrows-Wheeler 变换及其逆变换
DOI：
--
发表时间：
2012
期刊：
Annual Symposium on Combinatorial Pattern Matching
影响因子：
--
作者：
Enno Ohlebusch;Timo Beller;M. Abouelhoda
通讯作者：
M. Abouelhoda
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
R. Grossi;Ankur Gupta;J. Vitter
通讯作者：
R. Grossi;Ankur Gupta;J. Vitter
压缩后缀树：LCP 值的高效计算和存储
DOI：
--
发表时间：
2013
期刊：
JEAL
影响因子：
--
作者：
Simon Gog;Enno Ohlebusch
通讯作者：
Enno Ohlebusch
使用小波树在字符串中进行双向搜索
DOI：
--
发表时间：
2010
期刊：
Annual Symposium on Combinatorial Pattern Matching
影响因子：
--
作者：
T. Schnattinger;Enno Ohlebusch;Simon Gog
通讯作者：
Simon Gog
并行后缀排序
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
N. Futamura;S. Aluru;S. Kurtz
通讯作者：
S. Kurtz