Computing the Burrows-Wheeler Transform of a String and Its Reverse
Computing the Burrows-Wheeler Transform of a String and Its Reverse
复制标题
计算字符串的 Burrows-Wheeler 变换及其逆变换
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Abouelhoda
中科院分区：
文献类型：
--
作者：
Enno Ohlebusch;Timo Beller;M. Abouelhoda
本文的贡献是双重的。首先，我们提供了新的理论见解之间的关系字符串和它的逆：如果一个字符串的Burrows-Wheeler变换（BWT）已计算通过排序其后缀，然后BWT和最长的公共前缀数组的反向字符串可以从它派生没有后缀排序。此外，我们证明了一个字符串的最长公共前缀数组和它的逆是彼此的排列。其次，我们提供了一个并行算法，给定的BWT的字符串，计算BWT的反向速度比所有已知的（并行）后缀排序算法。一些生物信息学应用将从中受益。
The contribution of this paper 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 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.