CAJ | 학술논문

基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的,未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法,给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题,利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测.
기인조이위배서재기인조중조배서계산연구중점유중요위치.교호형이위화비교호형이위균위이위적특수형식.목전견도적다충이위배서산법균시침대교호형이위이득도적,미견기인조일반이위배서계산적연구결과.문중토론포괄교호형이위화비교호형이위적일반이위배서문제적구해방법,급출해문제적일개다항식시간산법.산법적관건재우장일반이위배서문제재선성시간내귀약위교호형이위배서문제,이용교호형이위배서적산법래구해일반이위배서.작자적산법증실료Ozery-Flato등관우일반이위배서문제가이다항식시간해결적시측.
Sorting genomes by translocations plays an important role in the research of genome rearrangement.Transloeation is a prevalent rearrangement event in the evolution of multi-ehromosomal species which exchanges ends between two chromosomes.Translocations include reciprocal 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.