臺灣博碩士論文加值系統

演化樹是用來描述物種間的相對關係, 而演化樹的建立可以根據多種不同的標準, 本篇我們要使用OLS(original least square)的標準以及branch-and-bound演算法去建造一棵具最小square error的演化.

A phylogenetic tree, also called an evolutionary tree, is a tree showing the
evolutionary interrelationships among various species that are believed to
have a common ancestor. In a phylogenetic tree, each node with descendants
represents the most recent common ancestor of the descendants, with
edge lengths sometimes corresponding to time estimates. In this thesis, we
consider the related problem that is given a distance matrix which represent
distnace among pairwise species and reconstructs the evolutionary tree of
these species under the criterion called OLS (Original Least Square error).
To find the optimal tree under OLS criterion, we need to cinsider a huge
searching spcae. So we will give a branch-and-bound algorithm to find the
optimal tree in this paper.

Contents
1 Introduction 5
2 Preliminaries 9
3 A Branch-and-Bound Algorithm 14
3.1 The basic concept . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 The branch-and-bound algorithm . . . . . . . . . . . . . . . . 17
3.3 An example illustrating branch-and-bound algorithm . . . . . 19
4 Improvement 22
4.1 The persistent data structure . . . . . . . . . . . . . . . . . . 22
4.2 Speedup odinary least square error metohd . . . . . . . . . . . 24
5 Experimental Results 29
5.1 The Environment of the Experiments . . . . . . . . . . . . . . 29
6 Concluding Remarks 31

Bibliography
[1] David Bryant and Peter Waddell. Rapid evaluation of least-squares
and minimum-evolution criteria on phylogenetic trees. Mol. Biol. Evol,
15:1346–1359, 1998.
[2] M. Bulmer. Use of the method of generalised least squares in reconstructing
phylogenies from sequence data. Mol. Biol. Evol., 8:868–883,
1991.
[3] L. Cavalli-Sforza and A. Edwards. Phylogenetic analysis models and
estimation procedures. Evolution, 32:550–570, 1967.
[4] JR Driscoll, N Sarnak, DD Sleator, and RE Tarjan. Making data structures
persistent. Journal of Computer and System Science, 38:86–124,
1989.
[5] MFarach, S Kannan, and TWarnow. A robust model for finding optimal
evolutionary trees. Algorithmica, 13:155–179, 1995.
[6] J. Felsenstein. Evolutionary trees from dna sequences:a maximum likelihood
approach. Journal of Molecular Evolution, 17:368–376, 1981.
[7] J. Felsenstein. Phylogenies from molecular sequences: inference and
reliability. Annu. Rev. Genet, 22:521–565, 1988.
[8] Margoliash E Fitch WM. Construction of phylogenetic trees. Science,
155:279–84, 1967.
[9] M. K. Kuhner and J. Felsenstein. A simulation study of phylogeny
algorithms under equal and unequal evolutionary rates. volume 11, pages
459–468, 1994.
[10] M. Farach B. Narayanan M. Paterson M. Thorup R. Agarwala, V. Bafna.
On the approximability of numerical taxonomy (fitting distances by tree
metrics). SIAM J. Comput, 28:1073–1085, 1999.
[11] E. Schroder. Vier combinatorische probleme. Z. Math.Phys, 15:361–376,
1870.
[12] Smith TF and Waterman MS. Identification of common molecular subsequences.
J Mol Biol, 147:195–197, 1981.
[13] Day WH. Computational complexity of inferring phylogenies from dissimilarity
matrices. Bull Math Biol, 49:461–467, 1987.