Constructing Evolutionary Trees - Algorithms and Complexity
(2001)- Abstract
- In this thesis three general problems concerning construction of evolutionary trees are considered. Algorithms for the problems are presented and the complexity of the problems is investigated.
The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. Different algorithms for the problem are given, including an optimal algorithm for constructing evolutionary trees and an optimal algorithm for merging two evolutionary trees. Matching lower bounds are also provided.
The second part of the thesis presents results related to the inferred consensus tree problem. The optimization version of the problem is shown to be... (More) - In this thesis three general problems concerning construction of evolutionary trees are considered. Algorithms for the problems are presented and the complexity of the problems is investigated.
The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. Different algorithms for the problem are given, including an optimal algorithm for constructing evolutionary trees and an optimal algorithm for merging two evolutionary trees. Matching lower bounds are also provided.
The second part of the thesis presents results related to the inferred consensus tree problem. The optimization version of the problem is shown to be NP-complete and two heuristic algorithms are presented. Further, the ordered version of the problem is studied.
In the last part of the thesis the complexity of the maximum homeomorphic subtree problem is examined. The problem is shown to be hard to approximate, unless P=NP, even for trees of constant height, whereas a constant approximation ratio is obtained in case of a constant number of trees of constant height. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/20178
- author
- Östlin, Anna LU
- supervisor
- opponent
-
- Halldorsson, Magnus
- organization
- publishing date
- 2001
- type
- Thesis
- publication status
- published
- subject
- keywords
- Computer science, Maximum homeomorphic subtrees, Consensus trees, Experiment model, Evolutionary trees, Complexity, Computational biology, Algorithms, Data structures, numerical analysis, systems, control, Datalogi, numerisk analys, system, kontroll, Biology, Biologi
- pages
- 99 pages
- publisher
- Department of Computer Science, Lund University
- defense location
- Building E at LTH, Room E:B
- defense date
- 2001-06-01 10:15:00
- ISBN
- 91-628-4772-4
- language
- English
- LU publication?
- yes
- id
- 50d3b2f1-3890-494e-9ba8-b3d9e6eaaaa9 (old id 20178)
- date added to LUP
- 2016-04-01 16:35:28
- date last changed
- 2021-05-06 08:31:46
@phdthesis{50d3b2f1-3890-494e-9ba8-b3d9e6eaaaa9,
abstract = {{In this thesis three general problems concerning construction of evolutionary trees are considered. Algorithms for the problems are presented and the complexity of the problems is investigated.<br/><br>
<br/><br>
The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. Different algorithms for the problem are given, including an optimal algorithm for constructing evolutionary trees and an optimal algorithm for merging two evolutionary trees. Matching lower bounds are also provided.<br/><br>
<br/><br>
The second part of the thesis presents results related to the inferred consensus tree problem. The optimization version of the problem is shown to be NP-complete and two heuristic algorithms are presented. Further, the ordered version of the problem is studied.<br/><br>
<br/><br>
In the last part of the thesis the complexity of the maximum homeomorphic subtree problem is examined. The problem is shown to be hard to approximate, unless P=NP, even for trees of constant height, whereas a constant approximation ratio is obtained in case of a constant number of trees of constant height.}},
author = {{Östlin, Anna}},
isbn = {{91-628-4772-4}},
keywords = {{Computer science; Maximum homeomorphic subtrees; Consensus trees; Experiment model; Evolutionary trees; Complexity; Computational biology; Algorithms; Data structures; numerical analysis; systems; control; Datalogi; numerisk analys; system; kontroll; Biology; Biologi}},
language = {{eng}},
publisher = {{Department of Computer Science, Lund University}},
school = {{Lund University}},
title = {{Constructing Evolutionary Trees - Algorithms and Complexity}},
year = {{2001}},
}