基因组一般移位排序问题的多项式时间算法  

Polynomial-Time Algorithm for Sorting Genomes by Generalized Translocations

作　　者：尹晓[1] 朱大铭[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101

出　　处：《计算机学报》2010年第5期785-796,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(60573024;60970003;60603007);教育部博士点基金(20090131110009)资助

摘　　要：基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的,未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法,给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题,利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测.Sorting genomes by translocations plays an important role in the research of genome rearrangement. Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. Translocations include recip- rocal translocations and non-reciprocal translocations. Translocation sorting problem asks to find a shortest sequence of translocations to transform one genome into another. Several polynomial algorithms have been presented, all of them only allowing reciprocal translocations. Thus they can only be applied to a pair of genomes having the same set of chromosome ends. Such a restriction can be removed if non-reciprocal translocations are also allowed. In this paper, the authors study for the problem of sorting by generalized translocations, which allows both reciprocal and non-reciprocal translocations, and present a polynomial-time algorithm for this problem, in which the problem of sorting by generalized translocations is reduced in linear time to the problem of sorting by reciprocal translocations. This algorithm confirms Ozery-Flato＇s conjecture that sorting by generalized translocations could be solved in polynomial time.

关 键 词：算法 基因组重组 移位 移位距离 计算生物学 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]