The transposition median problem is NP-complete

During recent years, the genomes of more and more species have been sequenced, providing data for phylogenetic reconstruction based on genome rearrangement measures, where the most important distance measures are the reversal distance and the transposition distance. The two main tasks in all phylogenetic reconstruction algorithms are to calculate pairwise distances and to solve the median of three problem. While the reversal distance problem can be solved in linear time, the reversal median problem has been proven to be NP-complete. The status of the transposition distance problem is still open, but it is conjectured to be more difficult than the reversal problem. This, in turn, also suggests that the transposition median problem is NP-complete. However, this conjecture could not yet be proven. We have now succeeded in giving a non-trivial proof for the NP-completeness of the transposition median problem.