Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach

DOI10.1016/J.JDA.2004.08.012MaRDI QIDQ2569412zbMATH OpenOpenAlexFDO

Authors M. C. Sobrinho, Eugenia T. G. Oliveira, Lorena S. Soares, Adilton G. Oliveira, Thelmo E. S. Martins, Tiago Fonseca, Maria Emilia Machado Telles Walter

Publication date 27 October 2005

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2004.08.012

zbMATH Keywords

transpositiontime complexitycycle graphalgorithm of Bafna and Pevzner

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20) Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• Working on the problem of sorting by transpositions on genome rearrangements
• Extension of the Bafna-Pevzner theory for the transposition sorting problem
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• An approximation algorithm for sorting by reversals and transpositions
• A simpler 1.5-approximation algorithm for sorting by transpositions

Cites work

• A simpler 1.5-approximation algorithm for sorting by transpositions
• Extension of the Bafna-Pevzner theory for the transposition sorting problem
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• Working on the problem of sorting by transpositions on genome rearrangements

Cited in

(5)

• Working on the problem of sorting by transpositions on genome rearrangements
• Implementation of bubble sort and the odd-even transposition sort on a rack of transputers
• An audit tool for genome rearrangement algorithms
• Rearrangement events on circular genomes
• Extension of the Bafna-Pevzner theory for the transposition sorting problem

This page was built for publication: Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2569412)