Reversal and transposition medians

DOI10.1016/j.tcs.2006.12.006zbMath1164.68041OpenAlexW1964746814MaRDI QIDQ1022594

Niklas Eriksen

Publication date: 22 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.12.006

zbMATH Keywords

mediantranspositiongenome rearrangementreversal

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problems related to evolution (92D15) Approximation algorithms (68W25)

Related Items (1)

The transposition median problem is NP-complete

Uses Software

• GRAPPA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• Steps toward accurate reconstructions of phylogenies from gene-order data.
• Estimating the expected reversal distance after a fixed number of reversals
• Transforming cabbage into turnip
• Generating a random permutation with random transpositions
• Sorting by Transpositions
• Finding an Optimal Inversion Median: Experimental Results
• On the Practical Solution of the Reversal Median Problem
• Genome Rearrangements and Sorting by Reversals
• STEINER POINTS IN THE SPACE OF GENOME REARRANGEMENTS
• On approximation properties of the Independent set problem for degree 3 graphs

This page was built for publication: Reversal and transposition medians