Session I.3 - Graph Theory and Combinatorics
Poster
Sorting Signed Permutations by Tandem Duplication Random Loss and Inverse Tandem Duplication Random Loss
Bruno J. Schmidt
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Tandem duplication random loss (TDRL) and inverse tandem duplication random loss (iTDRL) are mechanisms of mitochondrial genome rearrangement that can be modeled as simple operations on signed permutations. Informally, they comprise the duplication of a subsequence of a permutation, where in the case of iTDRL the copy is inserted with inverted order and signs. In the second step, one copy of each duplicate element is removed, such that the result is again a signed permutation. The TDRL/iTDRL sorting problem consists in finding the minimal number of TDRL or iTDRL operations necessary to convert the identity permutation $\iota$ into a given permutation $\pi$. We introduce a simple signature, called the misc-encoding, of permutation $\pi$. This construction is used to design an $\mathcal{O}(n\log{}n)$ algorithm to solve the TDRL/iTDRL sorting problem
Joint work with Tom Hartmann (Bioinformatics Group, Department of Computer Science &, Interdisciplinary Center for Bioinformatics, Leipzig University, Leipzig, Germany), Peter F. Stadler (Bioinformatics Group, Department of Computer Science & Interdisciplinary Center for Bioinformatics Leipzig University, Leipzig, Germany; Max Planck Institute for Mathematics in the, Sciences, Leipzig, Germany; Center for Scalable Data Analytics and Artificial Intelligence, Dresden/Leipzig, Germany; Department of Theoretical Chemistry, University of Vienna, Vienna, Austria; Facultad de Ciencias, Universidad National de Colombia, Bogota, Colombia; Santa and Fe Institute, Santa Fe, NM, USA).