2026-07-24T10:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11039 2024-03-06T10:47:27Z ddc:004 open_access

A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation Zoller, Roni Zehavi, Meirav Ziv-Ukelson, Michal Gene tree Species tree Reconciliation An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss and mobilization patterns of the gene within the genomes in which it disseminates. In this paper, we formalize this microbiological goal as a new pattern-matching problem in the domain of Gene tree and Species tree reconciliation, denoted "Reconciliation-Scenario Altering Mutation (RSAM) Discovery". We propose an O(m * n * k) time algorithm to solve this new problem, where m and n are the number of vertices of the input Gene tree and Species tree, respectively, and k is a user-specified parameter that bounds from above the number of optimal solutions of interest. The algorithm first constructs a hypergraph representing the k highest scoring reconciliation scenarios between the given Gene tree and Species tree, and then interrogates this hypergraph for subtrees matching a pre-specified RSAM Pattern. Our algorithm is optimal in the sense that the number of hypernodes in the hypergraph can be lower bounded by Omega(m * n * k). We implement the new algorithm as a tool, denoted RSAM-finder, and demonstrate its application to the identification of RSAMs in toxins and drug resistance elements across a dataset spanning hundreds of species. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roni Zoller and Meirav Zehavi and Michal Ziv-Ukelson 2019 Is Part Of LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2019.9 urn:nbn:de:0030-drops-110398 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.9 eng https://creativecommons.org/licenses/by/3.0/legalcode