有向基因组反转和转位排序最小权重问题的1.5k近似算法

1.5k-approximation Algorithm for Minimal Weight of Sorting Signed Genomes by Reversals and Transpositions

随着快速测序技术的发展,基因组重组排序问题已经成为计算生物学的一个重要研究领域.基因组重组操作包括反转、转位和移位操作.其研究目标是寻找最短的重组操作序列,将一种基因组转变为另一种基因组.考虑重组操作所花费的费用,讨论了有向基因组反转和转位排序的最小权重问题,证明该问题的一个下界,并给出一个近似度为1.5k的近似算法,其中k是一个常数,且k≥1.

With the development of fast sequencing techniques,the problem of sorting by genomes rearrangements has become an important research area of computational biology.There are three classical genomes rearrangements operations： reversal,transposition and translocation.The goal is to find the shortest sequence of genome arrangements operations that transform one genome into another.In this paper,we discuss minimal weight of sorting signed genomes by reversals and transpositions through considering the cost of the genomes rearrangements operations,and establish a lower bound for the problem and give a 1.5k-approximation algorithm,where k is a constant and k≥ 1.