臺灣博碩士論文加值系統

對於以實數為量測距離單位的演化樹建構一直以來有很多不同模型被提出，然而，最小權重演化樹〈Minisize Evolutionary Tree〉，目前尚無人提出一個系統化求尋最佳解的方式，在本篇論文裡我們利用分支及設限演算法〈Branch-and-Bound Algorithm〉搭配保持資料結構〈Persistent Data Structure〉求尋該問題的最佳解。並且，對於固定樹型最小權重演化樹的問題我們也提出了三種不同的求算較低解〈Lower Bound〉的方式以做為後續繼續研究的基礎。

The construction of evolutionary trees for a given matrix of interleaf dis-
tance is a fundamental problem in computational biology. There are many
constructing criteria for distance based evolutionary trees. In this thesis, we
consider the relate problem where we given a matrix with respect to pairwise
species distance and would like to ¯nd a tree whose total branch weight is
minimize under the constraints of Minisize tree. Usually, we call such prob-
lem as Minisize (Minimum Size) Evolutionary Tree Problem. This problem
is ¯rst proposed by Beyer et al.; they use linear programming to evaluate the
branch weights of the tree whenever tree topology is decided. Later, Water-
man et al. employ linear programming and greedy algorithm to ¯nd the local
optimal Minisize tree with respect to input distance matrix. So far, no one
has yet presented a systematic appaoach for searching the optimal tree under
the Minisize criterion. Therefore, we provide a branch-and-bound algorithm
with persistent data structure for Minisize Evolutionary Tree Problem. For
further study, we also proposed the three lower bound evalution methods for
the version of Fixed Topology Minisize Evolutionary Tree Problem

1 Introduction 1
2 Preliminaries 6
3 The Branch-and-Bound Algorithm with Persistent Data Struc-
ture 10
3.1 The Branch-and-Bound Algorithm . . . . . . . . . . . . .. 11
3.2 The Linear Programming for An Evolutionary Tree . . . .. . 16
3.3 Persistent Data Structure . . . . . . . . . . . . . . .. . 18
4 Three Lower Bounds for Fixed Topology Minisize Evolution-
ary Tree 21
4.1 Lower Bound by Circular Order of Tree Method . . . . . . . 22
4.2 Lower Bound by Neighbor-Merging Method . . . . . . . . . . 23
4.3 Lower Bound by Reducing Constraints Method . . . . . . . . 29
5 Experimental Results 32
6 Conclusion 33

[1] RICHA AGARWALA, VINEET BAFNA, MARTIN FARACH, MIKE
PATERSON, and MIKKEL THORUP. On the approximability of nu-
merical taxonomy; ¯tting distances by tree metrics. SIAM Journal on
Computing, pages 365{372, 1996.
[2] WA Beyer, ML Stein, TF Smith, and SM Ulam. A molecular sequence
metric and evolutionary trees. Math. Bioscience, 19:9{25, 1974.
[3] David Bryant and Peter Waddell. Rapid evaluation of least-squares
and minimum-evolution criteria on phylogenetic trees. Mol. Biol. Evol,
15:1346{1359, 1998.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clif-
ford Stein. Introduction to Algorithms, pages 790{803. MIT Press, 2nd
edition, 2001.
[5] WHE Day. Computational complexity of inferring phylogenies from
dissimilarity matrices. Bull Math Biol, 49:461{467, 1987.
[6] Richard Desper and Olivier Gascue. Fast and accurate phylogeny recon-
struction algorithms based on the minimum-evolution principle. Journal
of Computational Biology, 9:687{705, 2002.
34
[7] JR Driscoll, N Sarnak, DD Sleator, and RE Tarjan. Making data struc-
tures persistent. Journal of Computer and System Science, 38:86{124,
1989.
[8] M Farach, S Kannan, and TWarnow. A robust model for ¯nding optimal
evolutionary trees. Algorithmica, 13:155{179, 1995.
[9] JS Farris. Estimating phylogenetic trees from distance matrices. Am.
Nat, 106:645{668, 1972.
[10] Kidd KK and Sgaramella-Zonta LA. Phylogenetic analysis: concepts
and methods. Am J Hum Genet, 23:235{252, 1971.
[11] Chantal Korostensky and Gaston H. Gonnet. Using traveling salesman
problem algorithms for evolutionary tree construction. Mol. Biol. Evol,
16:619{267, 2000.
[12] Lopaka Lee. GNU Linear Programming Kit, 4.8 edition, 2005.
http://directory.fsf.org/libs/glpk.html.
[13] Cavalli-Sforza LL and Edwards AW. Phylogenetic analysis. models and
estimation procedures. Am J Hum Genet, 19:233{257, 1967.
[14] Roderic D. M. Page and Edward C. Holmes. Molecular Evolution: A
Phylogenetic Approach, pages 11{36. Blackwell Publishers, 1nd edition,
1998.
[15] N Saitou, M Nei, and LS Lerman. The neighbor-joining method: a new
method for reconstructing phylogenetic trees. Mol. Biol. Evol, 4:406{
425, 1987.
[16] Smith TF and Waterman MS. Identi¯cation of common molecular sub-
sequences. J Mol Biol, 147:195{197, 1981.
35
[17] Robert J. Vanderbei. Linear Programming: Foundations and Exten-
sions, pages 13{42. Boston : Kluwer Academic Publishers, 2nd edition,
2001.
[18] MS Waterman, TF Smith, M Singh, and WA Beyer. Additive evolu-
tionary trees. J. Theor. Biol, 64:1999{213, 1977.
[19] Fitch WM and Margoliash E. Construction of phylogenetic trees. Algo-
rithmica, 20:279{284, 1967.
[20] Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang. Approximation
and exact algorithms for constructing minimum ultrametric trees from
distance matrices. Journal of Combinatorial Optimization, 3:199{211,
1999.