OASIcs.GCB.2013.110.pdf
- Filesize: 0.62 MB
- 15 pages
Document
Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment
Authors
-
Part of:
Volume:
German Conference on Bioinformatics 2013 (GCB 2013)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2013-09-09
Cite As Get BibTex
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)
https://doi.org/10.4230/OASIcs.GCB.2013.110
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.
Subject Classification
Keywords
- minisatellite alignment
- dynamic programming
- ambiguity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads