Genome rearrangements and sorting by reversals
Genome rearrangements and sorting by reversals
复制标题
DOI：
10.1137/s0097539793250627
复制
发表时间：
1996-04-01
影响因子：
1.6
通讯作者：
Pevzner, PA
中科院分区：
文献类型：
--
作者：
Bafna, V;Pevzner, PA
分子生物学中的序列比较正处于重大范式转变的开始——从基于局部突变（即核苷酸的插入、删除和替换）的基因比较转变为基于全局重排（即片段的倒置和转位）的染色体比较。序列比较的经典方法不适用于全局重排，并且在计算机科学中，如果允许全局重排，则对序列之间的编辑距离知之甚少。在最简单的形式中，基因重排问题对应于通过反转排序，即使用任意片段的反转对数组进行排序。最近，Kececioglu 和 Sankoff 给出了第一个近似算法，用于通过保证误差界限 2 的反转排序，并确定了与染色体重排相关的开放问题。这些问题之一是戈兰关于对称群反转直径的猜想。本文证明了这个猜想。此外，还研究了两个随机排列之间的预期反转距离问题。显示两个随机排列之间的反转距离非常接近反转直径，从而表明反转距离在分子进化研究中提供了相关序列和不相关序列之间的良好分离。基因重排问题迫使我们考虑符号排列的逆转，因为 DNA 中的基因可能是正向或负向的。提出了一种用于有符号排列的近似算法，其提供了3/2的性能保证。最后，使用有符号排列方法，描述了一种通过反转排序的近似算法，其实现了7/4的性能保证。
Sequence comparison in molecular biology is in the beginning of a major paradigm shift-a shift from gene comparison based on local mutations (i.e., insertions, deletions, and substitutions of nucleotides) to chromosome comparison based on global rearrangements (i.e., inversions and transpositions of fragments). The classical methods of sequence comparison do not work for global rearrangements, and little is known in computer science about the edit distance between sequences if global rearrangements are allowed. In the simplest form, the problem of gene rearrangements corresponds to sorting by reversals, i.e., sorting of an array using reversals of arbitrary fragments. Recently, Kececioglu and Sankoff gave the first approximation algorithm for sorting by reversals with guaranteed error bound 2 and identified open problems related to chromosome rearrangements. One of these problems is Gollan's conjecture on the reversal diameter of the symmetric group. This paper proves the conjecture. Further, the problem of expected reversal distance between two random permutations is investigated. The reversal distance between two random permutations is shown to be very close to the reversal diameter, thereby indicating that reversal distance provides a good separation between related and nonrelated sequences in molecular evolution studies. The gene rearrangement problem forces us to consider reversals of signed permutations, as the genes in DNA could be positively or negatively oriented. An approximation algorithm for signed permutation is presented, which provides a performance guarantee of 3/2 Finally, using the signed permutations approach, an approximation algorithm for sorting by reversals is described which achieves a performance guarantee of 7/4.