Details zur Publikation

Kategorie Textpublikation
Referenztyp Zeitschriften
DOI 10.1109/TCBB.2018.2831661
Volltext Akzeptiertes Manuskript
Titel (primär) An exact algorithm for sorting by weighted preserving genome rearrangements
Autor Hartmann, T.; Bernt, M. ORCID logo ; Middendorf, M.
Quelle IEEE/ACM Transactions on Computational Biology and Bioinformatics
Erscheinungsjahr 2019
Department MOLSYB
Band/Volume 16
Heft 1
Seite von 52
Seite bis 62
Sprache englisch
Keywords Genome rearrangements; transposition; inversio; tandem duplication random loss; mitochondria; fungi; common interval

The preserving Genome Sorting Problem (pGSP) asks for a shortest sequence of rearrangement operations that transforms a given gene order into another given gene order by using rearrangement operations that preserve common intervals, i.e., groups of genes that form an interval in both given gene orders. The wpGSP is the weighted version of the problem were each type of rearrangement operation has a weight and a minimum weight sequence of rearrangement operations is sought. An exact algorithm – called CREx2 – is presented, which solves the wpGSP for arbitrary gene orders and the following types of rearrangement operations: inversions, transpositions, inverse transpositions, and tandem duplication random loss operations. CREx2 has a (worst case) exponential runtime, but a linear runtime for problem instances where the common intervals are organized in a linear structure. The efficiency of CREx2 and its usefulness for phylogenetic analysis is shown empirically for gene orders of fungal mitochondrial genomes.

dauerhafte UFZ-Verlinkung
Hartmann, T., Bernt, M., Middendorf, M. (2019):
An exact algorithm for sorting by weighted preserving genome rearrangements
IEEE-ACM Trans. Comput. Biol. Bioinform. 16 (1), 52 - 62 10.1109/TCBB.2018.2831661