Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment

Löwes B, Giegerich R (2013)
In: German Conference on Bioinformatics 2013. Beißbarth T, Kollmar M, Leha A, Morgenstern B, Schultz A-K, Waack S, Wingender E (Eds); OpenAccess Series in Informatics (OASIcs), 34. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik: 110-124.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Herausgeber
; ; ; ; ; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
Titel des Konferenzbandes
German Conference on Bioinformatics 2013
Band
34
Seite
110 - 124
Konferenz
German Conference on Bioinformatics 2013
Konferenzort
Göttingen
Konferenzdatum
2013-09-10 – 2013-09-13
ISSN
PUB-ID

Zitieren

Löwes B, Giegerich R. Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment. In: Beißbarth T, Kollmar M, Leha A, et al., eds. German Conference on Bioinformatics 2013. OpenAccess Series in Informatics (OASIcs). Vol 34. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2013: 110-124.
Löwes, B., & Giegerich, R. (2013). Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment. In T. Beißbarth, M. Kollmar, A. Leha, B. Morgenstern, A. - K. Schultz, S. Waack, & E. Wingender (Eds.), OpenAccess Series in Informatics (OASIcs): Vol. 34. German Conference on Bioinformatics 2013 (pp. 110-124). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/OASIcs.GCB.2013.110
Löwes, B., and Giegerich, R. (2013). “Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment” in German Conference on Bioinformatics 2013, Beißbarth, T., Kollmar, M., Leha, A., Morgenstern, B., Schultz, A. - K., Waack, S., and Wingender, E. eds. OpenAccess Series in Informatics (OASIcs), vol. 34, (Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 110-124.
Löwes, B., & Giegerich, R., 2013. Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment. In T. Beißbarth, et al., eds. German Conference on Bioinformatics 2013. OpenAccess Series in Informatics (OASIcs). no.34 Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 110-124.
B. Löwes and R. Giegerich, “Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment”, German Conference on Bioinformatics 2013, T. Beißbarth, et al., eds., OpenAccess Series in Informatics (OASIcs), vol. 34, Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp.110-124.
Löwes, B., Giegerich, R.: Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment. In: Beißbarth, T., Kollmar, M., Leha, A., Morgenstern, B., Schultz, A.-K., Waack, S., and Wingender, E. (eds.) German Conference on Bioinformatics 2013. OpenAccess Series in Informatics (OASIcs). 34, p. 110-124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2013).
Löwes, Benedikt, and Giegerich, Robert. “Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment”. German Conference on Bioinformatics 2013. Ed. Tim Beißbarth, Martin Kollmar, Andreas Leha, Burkhard Morgenstern, Anne-Kathrin Schultz, Stephan Waack, and Edgar Wingender. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013.Vol. 34. OpenAccess Series in Informatics (OASIcs). 110-124.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar
ISBN Suche