1 Search Results for "Zoller, Roni"

Document
DOI: 10.4230/LIPIcs.WABI.2019.9
A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation

Authors: Roni Zoller, Meirav Zehavi, and Michal Ziv-Ukelson

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract
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.
Cite as

Roni Zoller, Meirav Zehavi, and Michal Ziv-Ukelson. A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{zoller_et_al:LIPIcs.WABI.2019.9,
  author =	{Zoller, Roni and Zehavi, Meirav and Ziv-Ukelson, Michal},
  title =	{{A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.9},
  URN =		{urn:nbn:de:0030-drops-110398},
  doi =		{10.4230/LIPIcs.WABI.2019.9},
  annote =	{Keywords: Gene tree, Species tree, Reconciliation}
}
  • Refine by Author
  • 1 Zehavi, Meirav
  • 1 Ziv-Ukelson, Michal
  • 1 Zoller, Roni

  • Refine by Classification
  • 1 Applied computing → Bioinformatics

  • Refine by Keyword
  • 1 Gene tree
  • 1 Reconciliation
  • 1 Species tree

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact