Determining the consistency of resolved triplets and fan triplets

Jesper Andreas Jansson; Andrzej Lingas; Ramesh Rajaby; Wing Kin Sung

doi:10.1089/cmb.2017.0256

Determining the consistency of resolved triplets and fan triplets

Jesper Andreas Jansson, Andrzej Lingas, Ramesh Rajaby, Wing Kin Sung

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

The R^+-F^+-Consistency problem takes as input two sets R⁺ and R^- of resolved triplets and two sets F⁺ and F^- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R⁺ ⊂ F⁺ and no elements in R^- ⊂ F^- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R^-=θ whose running time is linear in the size of the input and therefore optimal.

Original language	English
Pages (from-to)	740-754
Number of pages	15
Journal	Journal of Computational Biology
Volume	25
Issue number	7
DOIs	https://doi.org/10.1089/cmb.2017.0256
Publication status	Published - Jul 2018

Keywords

computational complexity
phylogenetic tree
rooted triplets consistency
tree algorithm

ASJC Scopus subject areas

Modelling and Simulation
Molecular Biology
Genetics
Computational Mathematics
Computational Theory and Mathematics

More information

10.1089/cmb.2017.0256

Cite this

@article{0045fcb7d2a646a782de43814d6996bf,

title = "Determining the consistency of resolved triplets and fan triplets",

abstract = "The R+-F+-Consistency problem takes as input two sets R+ and R- of resolved triplets and two sets F+ and F- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ⊂ F+ and no elements in R- ⊂ F- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R-=θ whose running time is linear in the size of the input and therefore optimal.",

keywords = "computational complexity, phylogenetic tree, rooted triplets consistency, tree algorithm",

author = "Jansson, {Jesper Andreas} and Andrzej Lingas and Ramesh Rajaby and Sung, {Wing Kin}",

year = "2018",

month = jul,

doi = "10.1089/cmb.2017.0256",

language = "English",

volume = "25",

pages = "740--754",

journal = "Journal of Computational Biology",

issn = "1066-5277",

publisher = "Mary Ann Liebert Inc.",

number = "7",

}

TY - JOUR

T1 - Determining the consistency of resolved triplets and fan triplets

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

AU - Rajaby, Ramesh

AU - Sung, Wing Kin

PY - 2018/7

Y1 - 2018/7

N2 - The R+-F+-Consistency problem takes as input two sets R+ and R- of resolved triplets and two sets F+ and F- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ⊂ F+ and no elements in R- ⊂ F- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R-=θ whose running time is linear in the size of the input and therefore optimal.

AB - The R+-F+-Consistency problem takes as input two sets R+ and R- of resolved triplets and two sets F+ and F- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ⊂ F+ and no elements in R- ⊂ F- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R-=θ whose running time is linear in the size of the input and therefore optimal.

KW - computational complexity

KW - phylogenetic tree

KW - rooted triplets consistency

KW - tree algorithm

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

U2 - 10.1089/cmb.2017.0256

DO - 10.1089/cmb.2017.0256

M3 - Journal article

C2 - 29451395

AN - SCOPUS:85050286790

SN - 1066-5277

VL - 25

SP - 740

EP - 754

JO - Journal of Computational Biology

JF - Journal of Computational Biology

IS - 7

ER -

Determining the consistency of resolved triplets and fan triplets

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this