摘要: 根据染色体重排可以重建物种进化历史。本文是一篇对于相关研究的综述。染色体重排是指基因从所在的染色体的正常位上易位至染色体的另一个位置上，或移动到另一条染色体上。染色体重排对物种分化来说是一个稳定、长存的影响因素，亲缘关系较近的物种之间染色体重排较少。染色体重排会导致基因在染色体上顺序的变化，因此可以根据基因顺序的相似程度来重建进化树。

在比较基因组时，基因序列通常以符号排列(Signed permutations)表示。常见的染色体重排有：倒位、转座、相互易位、染色体分裂和融合。倒位会打破两个相邻点（两个断点），转座会形成三个断点，易位会形成二个断点，而分裂会打破一个相邻点。从一个基因组变到另一个基因组所需的五个基本染色体重排操作的次数称为基因组距离。除此之外，还有DCJ距离，被定为DCJ操作的次数。一次DCJ操作会带来一个相邻点与另一个相邻点或端粒的一次重组。倒位、相互易位、染色体分裂和融合都可以通过一次DCJ操作来实现，而转座需要两次DCJ操作。DCJ距离可以通过定义一个二部图，并寻找其所含的环和奇数长路径的个数来计算。

系统发生树是一种常用的物种进化关系表示图。构建系统发生树的一个基因问题就是推断祖先基因组。通过现有物种染色体上的基因顺序可以推断它们祖先的基因顺序。常用的假设是祖先基因组应该离所有子代基因组的距离和最小。

许多物种的基因组在进化过程中发生过全基因组复制，而基因组二分（genome halving）就是要根据当前基因组推断复制前的基因组。基因组二分常会遇到多重解的情况，这时需要以另一个单拷贝基因组为模板来从多个解中挑选出一个最好的，这个过程被称为有指导的二分（guided halving）。除了二倍，基因组二分算法还可扩展到三倍、四倍甚至更多倍复制的情况。

以上问题的求解一般要求预知全基因组基因的顺序，但很多物种还目前还没有全基因组序列，只有一些测序的片断（contig）。这些片断中含有部分基因的局部顺序关系。由这些片断可以构建一个有向无环图，但有向无环图的比较却很难。另一个简单的策略就是直接把每个片断当作一个完整的染色体。

由于同源基因鉴定的错误，分析之前还需从片断库中选出一个兼容的片断集以最大地包含原有数据中的信息—MSR问题。这个问题可以通过转换成兼容图（compatible graph）中的最大权完全子图问题，或者矛盾图（conflict graph）中的最大权独立集问题。有时由于两个物种的基因顺序相差很大，还需要把一些相近的基因聚在一起考虑，文章回顾了基因聚类的一些问题。