1 Search Results for "Löwes, Benedikt"

Document
DOI: 10.4230/OASIcs.GCB.2013.110
Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment

Authors: Benedikt Löwes and Robert Giegerich

Published in: OASIcs, Volume 34, German Conference on Bioinformatics 2013

Abstract
Several algorithms have been suggested for minisatellite alignment. Their time complexity is high -- close to O(n^3) -- due to the necessary reconstruction of duplication histories. We investigate the uniqueness of optimal alignments computed under the common single-copy duplication model. To this extent, it is necessary to avoid ambiguity in the algorithm employed. We re-code the ARLEM algorithm in the form of a grammar, and apply a disambiguation technique which uses a mapping to a canonical representation of minisatellite alignments. Having arrived at a non-ambiguous algorithm this way, we demonstrate that the underlying model -- independent of the algorithm -- gives rise to an exorbitant number of different, co-optimal alignments when applied to real-world data. We conclude that alignment-free methods should be considered for minisatellite comparison.
Cite as

Benedikt Löwes and Robert Giegerich. Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment. In German Conference on Bioinformatics 2013. Open Access Series in Informatics (OASIcs), Volume 34, pp. 110-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{lowes_et_al:OASIcs.GCB.2013.110,
  author =	{L\"{o}wes, Benedikt and Giegerich, Robert},
  title =	{{Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment}},
  booktitle =	{German Conference on Bioinformatics 2013},
  pages =	{110--124},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-59-0},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{34},
  editor =	{Bei{\ss}barth, Tim and Kollmar, Martin and Leha, Andreas and Morgenstern, Burkhard and Schultz, Anne-Kathrin and Waack, Stephan and Wingender, Edgar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2013.110},
  URN =		{urn:nbn:de:0030-drops-42285},
  doi =		{10.4230/OASIcs.GCB.2013.110},
  annote =	{Keywords: minisatellite alignment, dynamic programming, ambiguity}
}
  • Refine by Author
  • 1 Giegerich, Robert
  • 1 Löwes, Benedikt

  • Refine by Classification

  • Refine by Keyword
  • 1 ambiguity
  • 1 dynamic programming
  • 1 minisatellite alignment

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

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