Complexity And Algorithms For Sorting Genomes By Flanked Transpositions

Genome rearrangement is an important area of computational biology.In the late 1980’s,Jeffrey Palmer and his colleagues discovered a remarkable and novel pattern of evolutionary change in plant organelles.They mapped the mitochondrial genomes of Brassica cderacea(cabbage)and Brassica campesttis(turnip),which are very closely related(many genes are 99%-99.9%identical).This discovery and many other studies confirmed that genome rearrangement is a common mode of molecular evolution,which has proven to be one of the central problems in the field of life science,gene medicine and disease treatment etc.Transposition,along with reversal and translocation,is a well-known genome rearrangement event that switches two consecutive segments on a genome,equivalently,move a segment to another position.The problem of sorting permutations by transpositions has attracted a great amount of interest since it was introduced by Bafna and Pevzner in 1995.However,empirical evidence has reported that,in many genomes,the participation of repeat segments is inevitable during genome evolution and the breakpoints where a transposition occurs are most likely accompanied by a triple of repeated segments.For example,a transposition will transform[r x r y z r]into[r y z r x r],where r appears three times.This type of transposition,which is called flanked transposition,unfortunately,was largely ignored until recently.In this paper,we investigate the problem of sorting by flanked transpositions,which requires a series of flanked transpositions to transform one genome into another.A genome is simple if any pair of repeats are adjacent at most once.Firstly,we present an O(n2)time algorithm to determine whether a simple genome of length n can be transformed into another by a series of flanked transpositions.Surprisingly,this algorithm can be extended to solve the decision problem on general genomes without any restriction.Towards the parsimonious scenario that uses a minimum number of flanked transpositions,we show that this corresponding optimization version is NP-hard,even if the two input genomes are simple and contain at most three duplicates of each repeat.Finally,we show that the decision algorithm on simple genomes guarantees an approximation ratio of 2 for the corresponding optimization version.