Balanced randomized tree splitting with applications to evolutionary tree constructions

Ming Yang Kao, Andrzej Lingas, Anna Östlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on eficient construction of evolutionary trees: a new upper time-bound on the problem of constructing an evolutionary tree from experiments, and a relatively fast approximation algorithm for the maximum agreement subtree problem for binary trees for which the maximum number of leaves in an optimal solution is large. We also present new lower bounds for the problem of constructing an evolutionary tree from experiments and for the problem of constructing a tree from an ultrametric distance matrix.

Original languageEnglish (US)
Title of host publicationSTACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
PublisherSpringer Verlag
Pages184-196
Number of pages13
ISBN (Print)354065691X, 9783540656913
StatePublished - Jan 1 1999
Event16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 - Trier, Germany
Duration: Mar 4 1999Mar 6 1999

Publication series

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

Other

Other16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999
CountryGermany
CityTrier
Period3/4/993/6/99

Fingerprint

Evolutionary Tree
Binary trees
Approximation algorithms
Experiments
Distance Matrix
Binary Tree
Fast Algorithm
Experiment
Approximation Algorithms
Leaves
Optimal Solution
Lower bound
Unknown

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Lingas, A., & Östlin, A. (1999). Balanced randomized tree splitting with applications to evolutionary tree constructions. In STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 184-196). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1563). Springer Verlag.
Kao, Ming Yang ; Lingas, Andrzej ; Östlin, Anna. / Balanced randomized tree splitting with applications to evolutionary tree constructions. STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, 1999. pp. 184-196 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{0274c39acd3a468f81a0a3d9d0651b06,
title = "Balanced randomized tree splitting with applications to evolutionary tree constructions",
abstract = "We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on eficient construction of evolutionary trees: a new upper time-bound on the problem of constructing an evolutionary tree from experiments, and a relatively fast approximation algorithm for the maximum agreement subtree problem for binary trees for which the maximum number of leaves in an optimal solution is large. We also present new lower bounds for the problem of constructing an evolutionary tree from experiments and for the problem of constructing a tree from an ultrametric distance matrix.",
author = "Kao, {Ming Yang} and Andrzej Lingas and Anna {\"O}stlin",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
isbn = "354065691X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "184--196",
booktitle = "STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
address = "Germany",

}

Kao, MY, Lingas, A & Östlin, A 1999, Balanced randomized tree splitting with applications to evolutionary tree constructions. in STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1563, Springer Verlag, pp. 184-196, 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999, Trier, Germany, 3/4/99.

Balanced randomized tree splitting with applications to evolutionary tree constructions. / Kao, Ming Yang; Lingas, Andrzej; Östlin, Anna.

STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag, 1999. p. 184-196 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1563).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Balanced randomized tree splitting with applications to evolutionary tree constructions

AU - Kao, Ming Yang

AU - Lingas, Andrzej

AU - Östlin, Anna

PY - 1999/1/1

Y1 - 1999/1/1

N2 - We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on eficient construction of evolutionary trees: a new upper time-bound on the problem of constructing an evolutionary tree from experiments, and a relatively fast approximation algorithm for the maximum agreement subtree problem for binary trees for which the maximum number of leaves in an optimal solution is large. We also present new lower bounds for the problem of constructing an evolutionary tree from experiments and for the problem of constructing a tree from an ultrametric distance matrix.

AB - We present a new technique called balanced randomized tree splitting. It is useful in constructing unknown trees recursively. By applying it we obtain two new results on eficient construction of evolutionary trees: a new upper time-bound on the problem of constructing an evolutionary tree from experiments, and a relatively fast approximation algorithm for the maximum agreement subtree problem for binary trees for which the maximum number of leaves in an optimal solution is large. We also present new lower bounds for the problem of constructing an evolutionary tree from experiments and for the problem of constructing a tree from an ultrametric distance matrix.

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

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

M3 - Conference contribution

AN - SCOPUS:84957059560

SN - 354065691X

SN - 9783540656913

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

SP - 184

EP - 196

BT - STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

PB - Springer Verlag

ER -

Kao MY, Lingas A, Östlin A. Balanced randomized tree splitting with applications to evolutionary tree constructions. In STACS 99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag. 1999. p. 184-196. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).