TY - JOUR

T1 - An optimal algorithm for computing all subtree repeats in trees

AU - Flouri, T.

AU - Kobert, K.

AU - Pissis, S. P.

AU - Stamatakis, A.

PY - 2014/5/28

Y1 - 2014/5/28

N2 - Given a labelled tree T, our goal is to group repeating subtrees of T into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple and time-optimal algorithm for solving this problem for unrooted unordered labelled trees and show that the running time of our method is linear with respect to the size of T. By unordered, we mean that the order of the adjacent nodes (children/neighbours) of any node of T is irrelevant. An unrooted tree T does not have a node that is designated as root and can also be referred to as an undirected tree. We show how the presented algorithm can easily be modified to operate on trees that do not satisfy some or any of the aforementioned assumptions on the tree structure; for instance, how it can be applied to rooted, ordered or unlabelled trees.

AB - Given a labelled tree T, our goal is to group repeating subtrees of T into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple and time-optimal algorithm for solving this problem for unrooted unordered labelled trees and show that the running time of our method is linear with respect to the size of T. By unordered, we mean that the order of the adjacent nodes (children/neighbours) of any node of T is irrelevant. An unrooted tree T does not have a node that is designated as root and can also be referred to as an undirected tree. We show how the presented algorithm can easily be modified to operate on trees that do not satisfy some or any of the aforementioned assumptions on the tree structure; for instance, how it can be applied to rooted, ordered or unlabelled trees.

KW - Subtree repeats

KW - Tree data structures

KW - Unrooted unordered labelled trees

UR - http://www.scopus.com/inward/record.url?scp=84899109441&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899109441&partnerID=8YFLogxK

U2 - 10.1098/rsta.2013.0140

DO - 10.1098/rsta.2013.0140

M3 - Review article

AN - SCOPUS:84899109441

SN - 1364-503X

VL - 372

JO - Philosophical Transactions of the Royal Society A Mathematical, Physical and Engineering Sciences

JF - Philosophical Transactions of the Royal Society A Mathematical, Physical and Engineering Sciences

IS - 2016

M1 - 20130140

ER -