Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
RNA Tree Comparisons via Unrooted Unordered Alignments
verfasst von : Nimrod Milo, Shay Zakov, Erez Katzenelson, Eitan Bachmat, Yefim Dinitz, Michal Ziv-Ukelson
Erschienen in: Algorithms in Bioinformatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We generalize some current approaches for RNA tree alignment, which are traditionally confined to
ordered rooted
mappings, to also consider
unordered unrooted
mappings. We define the
Homeomorphic Subtree Alignment
problem, and present a new algorithm which applies to several modes, including global or local, ordered or unordered, and rooted or unrooted tree alignments. Our algorithm generalizes previous algorithms that either solved the problem in an asymmetric manner, or were restricted to the rooted and/or ordered cases. Focusing here on the most general unrooted unordered case, we show that our algorithm has an
O
(
n
T
n
S
min (
d
T
,
d
S
)) time complexity, where
n
T
and
n
S
are the number of nodes and
d
T
and
d
S
are the maximum node degrees in the input trees
T
and
S
, respectively. This maintains (and slightly improves) the time complexity of previous, less general algorithms for the problem.
Supplemental materials, source code, and web-interface for our tool are found in
http://www.cs.bgu.ac.il/~negevcb/FRUUT
.