article · reposiTUm (TU Wien) · 2020
A Generalized Constrained Longest Common Subsequence Problem
Berger, Christoph
Cited by 0Open access
Abstract
Diese Arbeit beschäftigt sich mit dem Constrained Longest Common Subsequence (CLCS) Problem, welches eingeführt wurde, um die Ähnlichkeit verschiedener biologischer Sequenzen zu messen. Dabei wird für eine gegebene Menge von beliebigen Strings die längste gemeinsame Teilfolge an Zeichen gesucht, welche selbst wiederum einen bestimmten gegebenen String als Teilfolge enthält. Es handelt sich um eine Variante des gut untersuchten Longest Common Subsequence (LCS) Problems. Verschiedene Algorithmen sind bekannt um das CLCS Problem für genau zwei Strings (2CLCS) zu lösen, das allgemeine mCLCS Problem mit einer beliebigen Menge von Strings wurde bisher jedoch nur näherungsweise mit einem Approximationsverfahren gelöst. Das mCLCS Problem kann in der Biologie der Identifikation von Molekülgruppen dienen, deren Moleküle eine Gemeinsamkeit in Form einer bestimmten vorhandenen Teilstruktur aufweisen. In dieser Arbeit werden mehrere neue Methoden vorgestellt um das mCLCS Problem effektiv zu lösen. Wir präsentieren eine heuristische Beam Search in der Form eines generellen Suchframeworks sowie einen exakten A*-Algorithmus. Die Ergebnisse unserer Tests zeigen, dass unsere A*-Suche, geführt von bekannten Upper Bounds des LCS Problems, signifikant schneller im Lösen von 2CLCS Instanzen als bisherige Algorithmen ist. Beim mCLCS Problem mit mehreren Strings konnten von der A*-Suche kleine bis mittelgroße Instanzen gelöst werden. Für jene Instanzen, die von A* nicht gelöst werden können, schlagen wir den Einsatz von Beam Search vor. Zur Führung der Beam Search haben sich eine auf Wahrscheinlichkeitstheorie basierenden Heuristik, sowie eine Heuristik zur Berechnung der erwarteten Länge als besonders effektiv erwiesen. Diese Beam Search Konfigurationen konnten bei fast allen von der A*-Suche exakt gelösten Instanzen ebenfalls optimale Lösungen finden und waren dabei signifikant schneller als die A*-Suche.
Cite this paper
Berger, C. (2020). A Generalized Constrained Longest Common Subsequence Problem. reposiTUm (TU Wien).
Berger, Christoph. “A Generalized Constrained Longest Common Subsequence Problem.” reposiTUm (TU Wien), 2020.
Berger, Christoph. 2020. “A Generalized Constrained Longest Common Subsequence Problem.” reposiTUm (TU Wien).
Berger, C. (2020) ‘A Generalized Constrained Longest Common Subsequence Problem’, reposiTUm (TU Wien).
@article{berger2020generalized,
title = {{A Generalized Constrained Longest Common Subsequence Problem}},
author = {Berger, Christoph},
journal = {reposiTUm (TU Wien)},
year = {2020}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.