Genomic sorting with length-weighted reversals.
Current algorithmic studies of genome rearrangement ignore the length of reversals (or inversions); rather, they only count their number. We introduce a new cost model in which the lengths of the reversed sequences play a role, allowing more flexibility in accounting for mutation phenomena. Our focus is on sorting unsigned (unoriented) permutations by reversals; since this problem remains difficult (NP-hard) in our new model, the best we can hope for are approximation results. We propose an efficient, novel algorithm that takes (a monotonic function f of) length into account as an optimization criterion and study its properties. Our results include an upper bound of O(fn lg2n) for any additive cost measure f on the cost of sorting any n-element permutation, and a guaranteed approximation ratio of O(lg2n) times optimal for sorting a given permutation. Our work poses some interesting questions to both biologists and computer scientists and suggests some new bioinformatic insights that are currently being studied.
Department of Computer Science, Technion--Israel Institute of Technology, Haifa 32000, Israel. pinter@cs.technion.ac.il
Ron Y
RY
Pinter
Steven
S
Skiena
D000465:Algorithms; D000818:Animals; D002874:Chromosome Mapping / Q000379:methods; D019295:Computational Biology / Q000379:methods*; D003434:Crossing Over, Genetic; D019143:Evolution, Molecular; D006801:Humans