Sorting a permutation by transpositions (SPbT) is an important problem in bioinformtics. In this article, we improve the running time of the best known approximation algorithm for SPbT.
Get full access to this article
View all access options for this article.
References
1.
BafnaV., PevznerP.A.1998. Sorting by transpositions. SIAM J. Discrete Math., 11:224–240.
2.
ChristieD.A.1999. Genome rearrangement problem [Ph.D. dissertation]University of Glasgow: Glasgow, UK.
3.
EliasI., HartmanT.2006. A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans. Comput. Biol. Bioinform., 3:369–379.
FengJ., ZhuD.2007. Faster algorithms for sorting by transpositions and sorting by block interchanges. ACM Trans. Algorithms, 3,3.
6.
GuQ.-P., PengS., SudboroughI.H.1999. A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor. Comput. Sci., 210:327–339.
7.
HannenhalliS., PevznerP.A.1999. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM, 46:1–27.
8.
HartmanT., ShamirR.2006. A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput., 204:275–290.
9.
SleatorD.D., TarjanR.E.1985. Self-adjusting binary search trees. J. ACM, 32:652–686.
