有向基因组移位排序算法的比较与评测

Comparison and Evaluation of Algorithms for the Translocation Sorting of Signed Genomes

基因组重组是生物进化的一种重要模式。虽然其生物过程非常复杂,但可归结为三种基本操作:移位、反转和转位。移位排序问题要求计算从一个基因组转化为另一个基因组所需的最少移位次数以及相应的移位序列。对于有向基因组移位排序问题,目前有三个多项式时间算法。已有算法在分析偶隔离带时漏掉一种情况,从而导致对某些特殊实例的计算结果是不正确的。通过给出这种特殊情况下找有效移位的方法,用Java语言将三个算法实现为移位排序软件—SG-BT,其计算效率优于现有的移位排序软件CTRD。通过随机产生的实验数据对三个算法的计算性能进行了测试,结果表明,三个算法的计算效率在基因数为0-70000时基本相同,在基因数为80000-100000时才表现出差异,并且随着基因数的增加差异越发明显。通过进一步实验,分析了产生上述结果的原因。最后,用SGBT对人和老鼠的部分基因进行排序并给出排序结果。

Genome rearrangement is an important mode of the evolution of living things. Though the arrangement process is very complicated, there are three basic operations： translocation, reversal and transposition. The signed translocation problem is to find out the minimum number of translocation operations as well as the sequence of translocations required to transform one genome to another. As to this problem, there are three polynomial-time algorithms. The former algorithms omit a case when analyzing even-isolation. The omited case as well as the method to find a valid transloation in this case are presented in this paper. All the three algorithms are implemented to a software named SGBT, whose effenciency is better than the former software-CTRD. The computing performance of the three algorithms are compared and evaluated by analyzing the random data computed by SGBT. It is indicated that the computing efficiency of the three algorithms is almost the same when the number of genes is between 0 and 70,000. However, the difference can be seen when the number of genes is between 80,000 to 100000. Furthermore, the larger the number of genes is, the more palpable the difference is. Finally, the partial data of genomes of men and mice are sorted by SGBT and the result is given.