1 Search Results for "Chateau, Annie"


Document
Weighted Minimum-Length Rearrangement Scenarios

Authors: Pijus Simonaitis, Annie Chateau, and Krister M. Swenson

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


Abstract
We present the first known model of genome rearrangement with an arbitrary real-valued weight function on the rearrangements. It is based on the dominant model for the mathematical and algorithmic study of genome rearrangement, Double Cut and Join (DCJ). Our objective function is the sum or product of the weights of the DCJs in an evolutionary scenario, and the function can be minimized or maximized. If the likelihood of observing an independent DCJ was estimated based on biological conditions, for example, then this objective function could be the likelihood of observing the independent DCJs together in a scenario. We present an O(n⁴)-time dynamic programming algorithm solving the Minimum Cost Parsimonious Scenario (MCPS) problem for co-tailed genomes with n genes (or syntenic blocks). Combining this with our previous work on MCPS yields a polynomial-time algorithm for general genomes. The key theoretical contribution is a novel link between the parsimonious DCJ (or 2-break) scenarios and quadrangulations of a regular polygon. To demonstrate that our algorithm is fast enough to treat biological data, we run it on syntenic blocks constructed for Human paired with Chimpanzee, Gibbon, Mouse, and Chicken. We argue that the Human and Gibbon pair is a particularly interesting model for the study of weighted genome rearrangements.

Cite as

Pijus Simonaitis, Annie Chateau, and Krister M. Swenson. Weighted Minimum-Length Rearrangement Scenarios. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{simonaitis_et_al:LIPIcs.WABI.2019.13,
  author =	{Simonaitis, Pijus and Chateau, Annie and Swenson, Krister M.},
  title =	{{Weighted Minimum-Length Rearrangement Scenarios}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{13:1--13:17},
  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.13},
  URN =		{urn:nbn:de:0030-drops-110436},
  doi =		{10.4230/LIPIcs.WABI.2019.13},
  annote =	{Keywords: Weighted genome rearrangement, Double cut and join (DCJ), Edge switch, Minimum-weight quadrangulation}
}
  • Refine by Author
  • 1 Chateau, Annie
  • 1 Simonaitis, Pijus
  • 1 Swenson, Krister M.

  • Refine by Classification
  • 1 Applied computing → Bioinformatics

  • Refine by Keyword
  • 1 Double cut and join (DCJ)
  • 1 Edge switch
  • 1 Minimum-weight quadrangulation
  • 1 Weighted genome rearrangement

  • 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