TY - GEN

T1 - Computing the rooted triplet distance between galled trees by counting triangles

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

PY - 2012/7/4

Y1 - 2012/7/4

N2 - We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n leaves then the rooted triplet distance can be computed in o(n2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost- monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new related results that may be of independent interest.

AB - We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n leaves then the rooted triplet distance can be computed in o(n2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost- monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new related results that may be of independent interest.

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

U2 - 10.1007/978-3-642-31265-6_31

DO - 10.1007/978-3-642-31265-6_31

M3 - Conference article published in proceeding or book

SN - 9783642312649

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 385

EP - 398

BT - Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings

T2 - 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012

Y2 - 3 July 2012 through 5 July 2012

ER -