基因组重组排序算法综述

A Survey of Sorting Algorithms for Genome Rearrangements

随着快速测序技术的发展,对大规模DNA分子的研究与其中的基因相对次序有关。基因组重组是计算生物学的一个重要研究领域,是基因组在基因水平比较分析的基础。其研究目标是找最短的重组操作序列,将一种基因组转变为另一种基因组。基于分子生物学的实验证明,这种序列有助于估计不同基因组间的进化事件。基因组进化过程虽然非常复杂,但可用3种基本的重组操作模拟,即反转(reversal)、移位(translocation)和转位(transposition)。本文讨论了这些操作相关的重组算法以及各种排序距离的计算方法。

With the development of fast sequencing techniques, large-scale DNA molecules are investigated with respect to the relative order of genes in them. Genome rearrangement is an important area of computational biology, and bases the comparison analysis of genomes at the level of genes. The goal is to find the shortest sequence of genome arrangements operations that transform one genome into another. Such sequence is helpful to estimate the evolutionary events between different genomes, which is proved by many tests of molecule biology. Although the evolutionary process between genomes is very complicated, there are three basic rearrangement operations： reversal, translocation, transposition. In this paper, we discuss the rearrangement algorithms for these operations, and the methods to compute various types of sorting distances.