Sankoff D, Blanchette M
Centre de recherches mathématiques, Université de Montréal, Québec, Canada.
J Comput Biol. 1998 Fall;5(3):555-70. doi: 10.1089/cmb.1998.5.555.
Multiple alignment of macromolecular sequences generalizes from N = 2 to N > or = 3 the comparison of N sequences which have diverged through the local processes of insertion, deletion and substitution. Gene-order sequences diverge through non-local genome rearrangement processes such as inversion (or reversal) and transposition. In this paper we show which formulations of multiple alignment have counterparts in multiple rearrangement. Based on difficulties inherent in rearrangement edit-distance calculation and interpretation, we argue for the simpler "breakpoint analysis." Consensus-based multiple rearrangement of N > or = 3 orders can be solved exactly through reduction to instances of the Travelling Salesman Problem (TSP). We propose a branch-and-bound solution to TSP particularly suited to these instances. Simulations show how non-uniqueness of the solution is attenuated with increasing numbers of data genomes. Tree-based multiple alignment can be achieved to a great degree of accuracy by decomposing the tree into a number of overlapping 3-stars centered on the non-terminal nodes, and solving the consensus-based problem iteratively for these nodes until convergence. Accuracy improves with very careful initializations at the non-terminal nodes. The degree of non-uniqueness of solutions depends on the position of the node in the tree in terms of path length to the terminal vertices.
大分子序列的多重比对将N个通过插入、缺失和替换等局部过程而发生分化的序列的比较从N = 2推广到了N≥3。基因顺序序列则通过诸如倒位（或反转）和转座等非局部基因组重排过程发生分化。在本文中，我们展示了多重比对的哪些公式在多重重排中有对应物。基于重排编辑距离计算和解释中固有的困难，我们主张采用更简单的“断点分析”。N≥3个顺序的基于共识的多重重排可以通过简化为旅行商问题（TSP）的实例来精确求解。我们提出了一种特别适用于这些实例的TSP分支定界解决方案。模拟显示了随着数据基因组数量的增加，解决方案的非唯一性是如何减弱的。通过将树分解为以非终端节点为中心的多个重叠三星结构，并对这些节点迭代求解基于共识的问题，直到收敛，可以在很大程度上实现基于树的多重比对。在非终端节点进行非常仔细的初始化时，准确性会提高。解决方案的非唯一性程度取决于树中节点相对于终端顶点的路径长度的位置。
