Sorting by inversions, fast
As early as the mid 1930s, inversions (also called reversals) had been observed by Sturtevant as rearrangements that affect the order of genes on a chromosome 5, 6. By 1941, sequences of inversions were being computed by hand that solved the problem of sorting by inversions: give a minimum number of successive inversions that turn one gene order into another 7. It wasnt until 1995 that a polynomial time algorithm for sorting signed permutations by inversions was discovered 2.Subsequent algorithms 3, 1, 8 have improved the O(n(4)) running time for length n permutations, to O(n√nlogn). The latest step was taken by Tannier and Sagot 8, 9 who devised a novel scheme for avoiding certain problematic inversions (called unssfe inversions) within the framework of a data structure developed by Kaplan and Verbin 4. In this poster, we present an algorithm that runs in O(nlogn+kn) time where k is a parameter related to these so-called unsafe inversions. We show experimentally that although k is O(n) which implies a worst-case running time of O(n(2)) for our algorithm, k remains constant as n grows, yielding an average-case running time of O(nlogn).
inversion distance reversal distance genomic distance Hannenhalli-Pevzner
Krister M.Swenson Vaibhav Rajan Yu Lin Bernard M.E.Moret
Laboratory for Computational Biology and Bioinformatics, EPFL (Ecole Polytechnique Fédérale de Lausanne), Lausanne, Switzerland
国际会议
The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)
北京
英文
836
2009-01-01（万方平台首次上网日期，不代表论文的发表时间）