臺灣博碩士論文加值系統

建構演化樹是現今計算生物裡一個很重要的問題。釵h專家學者致力於研究此領域。其中一個較基本的問題是建構一個星狀拓樸的演化樹。假如有m個基因組，每個基因組間邊上的權重定義為反轉距離(reversal distance)。如何去建構一個星狀的樹，使得所有邊上權重的總和為最小。這就是所謂的反轉中值問題(Reversal Median Problem)。我們將實作一個分支設限演算法(branch-and-bound algorithm)以及展示它的效能。

Reconstructing phylogenetic tree is a crucial issue nowadays on the field of computational biology. Lots of researchers have devoted to this area. One of the basic problems is to construct the evolutionary tree as a star topology. Given m genomes and the weight between each pair of genomes on the edges is reversal distance, we want to construct a star tree such that the total sum of weights on the edges of the tree is minimum. It is called the Reversal Median Problem (RMP). We implement a branch-and-bound algorithm and show its performance.

1.Introduction……………………………………………1
2.Preliminary………………………………………………5
3.An Algorithm for Finding an Exact Median………9
3.1.Bounds…………………………………………………10
3.2.The Upper Bound of Reversal Distance…………12
3.3.The Branch and Bound Algorithm…………………14
3.4.Implementation………………………………………17
4.Experimental Results…………………………………22
5.Conclusion………………………………………………29

[1] D. A. Bader, B. M. E. Moret, and M. Yan. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology, 8(5):483–491, 2001.
[2] A. Bergeron. A very elementary presentation of the Hannenhalli-Pevzner theory. In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001), pages 106–117, 2001.
[3] A. Bergeron. A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics, 146:134–145, 2005.
[4] A. Bergeron, J. Mixtacki, and J. Stoye. Reversal distance without hurdles and fortresses. In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004), pages 388–399, 2004.
[5] P. Berman and S. Hannenhalli. Fast sorting by reversal. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM 1996), pages 168–185, 1996.
[6] P. Berman, S. Hannenhalli, and M. Karpinski. 1.375-approximation algorithm for sorting by reversals. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), pages 200–210, 2002.
[7] P. Berman and M. Karpinski. On some tighter inapproximability results. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP 1999), pages 200–209, 1999.
[8] G. Bourque and P. A. Pevzner. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Research, 12(1):26–36, 2002.
[9] A. Caprara. Sorting by reversals is difficult. In Proceedings of the First Annual International Conference on Research in Computational Molecular Biology (RECOM 1997), pages 75–83, 1997.
[10] A. Caprara. Formulations and hardness of multiple sorting by reversals. In Proceedings of the Third Annual International Conference on Computational Molecular Biology (RECOMB 1999), pages 84–93, 1999.
[11] A. Caprara. Sorting permutations by reversals and eulerian cycle decompositions. SIAM Journal on Discrete Mathematics, 12(1):91–110, 1999.
[12] A. Caprara. On the practical solution of the reversal median problem. In Proceedings of the First International Workshop on Algorithms in Bioinformatics (WABI 2001), pages 238–251, 2001.
[13] A. Caprara. The reversal median problem. INFORMS Journal on Computing, 15(1):93–113, 2003.
[14] H.-F. Chen and M.-S. Chang. Improvement of Branch and Bound Algorithms for Some Combinatorial Optimization Problems: Traveling Salesman Problem (TSP). Department of Computer Science and Information Engineering, National Chung Cheng University, Taiwan, R.O.C., 2003. Available at http://ufo.cs.ccu.edu.tw/project92/tsp/.
[15] D. A. Christie. Sorting permutations by block-interchanges. Information Processing Letters, 60(4):165–169, 1996.
[16] N. El-Mabrouk. Genome rearrangement by reversals and insertions/deletions of contiguous segments. In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), pages 222–234, 2000.
[17] R. Shamir H. Kaplan and R. E. Tarjan. A faster and simpler algorithm for sorting signed permutations by reversals. SIAM Journal of Computing, 29(3):880–892, 1999.
[18] S. Hannenhalli, C. Chappey, E. V. Koonin, and P. A. Pevzner. Genome sequence comparison and scenarios for gene rearrangements: A test case. Genomics, 30(2):299–311, 1995.
[19] S. Hannenhalli and P. A. Pevzner. Transforming cabbage into turnip : polynomial algorithm for sorting signed permutations by reversals). In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC 1995), pages 178–189, 1995.
[20] F. K. Hwang, D. S. Richards, and P. Winter. The steiner tree problem. Elsevier Science Publishers B.V., 1992.
[21] Y. C. Lin, C. L. Lu, H.-Y. Chang, and C. Y. Tang. An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species. Journal of Computational Biology, 12(1):102–112, 2005.
[22] K. M. Swenson M. Marron and B. M. E. Moret. Genomic distances under deletions and insertions. Theoretical Computer Science, 325(3):347–360, 2004.
[23] I. Mantin and R. Shamir. An Applet demonstration of An Algorithm for sorting signed permutation by reversals, 1999. Available at http://www.cs.tau.ac.il/~rshamir/GR/.
[24] M. Marron, K. M. Swenson, and B. M. E. Moret. Genomic distances under deletions and insertions. In Proceedings of the 9th Annual International Conference on Computing and Combinatorics (COCOON 2003), pages 537–547, 2003.
[25] B. M. E. Moret, A. C. Siepel, J. Tang, and T. Liu. Inversion medians outperform breakpoint medians in phylogeny reconstruction from geneorder data. In Proceedings of the Second International Workshop on Algorithms in Bioinformatics (WABI 2002), pages 521–536, 2002.
[26] M. Ozery-Flato and R. Shamir. Two notes on genome rearrangement. Journal of Bioinformatics and Computational Biology, 1(1):71–94, 2003.
[27] D. Sankoff and M. Blanchette. The median problem for breakpoints in comparative genomics. In Proceedings of the Third Annual International Conference on Computing and Combinatorics (COCOON 1997), pages 251–264, 1997.
[28] D. Sankoff and M. Blanchette. Multiple genome rearrangement and breakpoint phylogeny. Journal of Computational Biology, 5(3):555–570, 1998.
[29] D. Sankoff, G. Sundaram, and J. D. Kececioglu. Steiner points in the space of genome rearrangements. International Journal of Foundations of Computer Science, 7(1):1–9, 1996.
[30] Joao Setubal and Joao Meidanis. Introduction to computational molecular biology, chapter 7. PWS Publishing Company, 1997.
[31] A. C. Siepel. Exact algorithms for the reversal median problem. Master’s thesis, The University of New Mexico, Albuquerque, New Mexico, Dec. 2001.
[32] A. C. Siepel. An algorithm to enumerate all sorting reversals. In Proceedings of the Sixth Annual International Conference on Computational Biology (RECOM 2002), pages 281–290, 2002.
[33] A. C. Siepel. An algorithm to enumerate sorting reversals for signed permutations. Journal of Computational Biology, 10(3/4):575–597, 2003.
[34] A. C. Siepel and B. M. E. Moret. Finding an optimal inversion median: Experimental results. In Proceedings of the First International Workshop on Algorithms in Bioinformatics (WABI 2001), pages 189–203, 2001.
[35] J. Tang and B. M. E. Moret. Phylogenetic reconstruction from generearrangement data with unequal gene content. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS 2003), pages 37–46, 2003.
[36] J. Tang and B. M. E. Moret. Linear programming for phylogenetic reconstruction based on gene rearrangements. In Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM 2005), pages 406–416, 2005.
[37] J. Tang and M. E. Moret. Phylogenetic reconstruction from arbitrary gene-order data. In Proceedings of the Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE 2004), pages 592–599, 2004.
[38] J. Tang, M. E.Moret, A. C. Siepel, A. Caprara, D. A. Bader, T.Warnow, S. K. Wyman, and M. Yan. GRAPPA: Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms. TheUniversity of New Mexico and The University of Texas at Austin, 2.0 Editions, 2004. Available at http://www.cs.unm.edu/~moret/GRAPPA/.
[39] E. Tannier and M.-F. Sagot. Sorting by reversals in subquadratic time. In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004), pages 1–13, 2004.