Computing the rooted triplet distance between galled trees by counting triangles

Jesper Andreas Jansson, Andrzej Lingas

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings
Pages385-398
Number of pages14
DOIs
Publication statusPublished - 4 Jul 2012
Externally publishedYes
Event23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012 - Helsinki, Finland
Duration: 3 Jul 20125 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7354 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012
Country/TerritoryFinland
CityHelsinki
Period3/07/125/07/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this