Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
A New and Faster Method of Sorting by Transpositions
verfasst von : Maxime Benoît-Gagné, Sylvie Hamel
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Some of the classical comparisons of DNA molecules consists in computing rearrangement distances between them, i.e.: a minimal number of rearrangements needed to change a molecule into another. One such rearrangement is that of
transposition
. At this time, it is not known if a polynomial time algorithm exists to compute the exact transposition distance between two permutations. In this article, we present a new and faster method of sorting by transpositions. While there does exist better algorithms with regards to distance approximation, our approach relies on a simpler structure which makes for a significantly faster computation time, while keeping an acceptable close approximation.