Sorting Signed Genomes By Reversals And Transpositions

With the development of fast sequencing techniques,the problem of sorting by genomes rearrangements has become an important research area of computational biology and bioinformatics.The goal is to find the shortest sequence of genome arrangements operations that transform one genome into another.Based on experimenttal data accumulated by molecular biology,it proved that genomes rearrangement is a common mode for biological evolution,and is viewed as a better estimation of the affinity relations among species.There are three classical genomes rearrangements operations:reversal,transposition and translocation.Reversal and transposition operations always act on one chromosome, while a translocation operation acts on two chromosomes.In the past,people mainly paid attention to the genomes rearrangements involving single rearrangement operation;but the research on genomes rearrangements sorting by combined rearrangement operations was relatively slow.Recently,for the problem of sorting unsigned genomes by reversals and transpositions,Xiaowen Lou and Daming Zhu gave a 2.25-approximation algorithm;for the problem of sorting signed genomes by reversals and transposition,Hartman and Sharan gave a 1.5-approximation algorithm.In this paper,we firstly discuss the problem of sorting signed genomes by reversals and transpositions,and introduce the Hartman's 1.5-approximation algorithm.Considering the cost of the rearrangements operation,we also intorduce a new problem,called minimal weight of sorting signed genomes by reversals and transpositions,and the goal is to calculate the least cost of genome rearrangements operations that transform one genome into another.In this paper,we give a 1.5k-approximation algorithm for this problem.There are four creative points in this paper:1.We consider the cost of the rearrangements operation,and introduce a new problem,called minimal weight of sorting signed genomes by reversals and transpositions,and show its backgroud and research value.2.We prove a new lower bound for this problem.3.Based on this lower bound,we give a 1.5k-approximation algorithm for this problem. 4.We give a C++ implement of the 1.5-appxition algorithm for sorting signed genomes by reversals and transpositions and the 1.5k-appsoximation algorithm of minimal weight for sorting signed genomes by reversals and transpositions.