近年來，計算生物學在資訊科學已變成一個新的研究領域。在基因組重排研究中，基因組的序列化與比較是較具挑戰性的主題。雖然在基因組重排問題中，兩個基因組的比較已被廣泛的研究，但建構多個物種間演化過程的演算法還是大量被需要的。在本論文中，我們研究多重基因組重排問題，並探討有關這個問題目前的研究。多重基因組重排問題是去找一個用來描述多個物種間演化情景的演化樹。此外，我們研究與實作一個有關有號排列反轉排序距離計算的演算法。這個演算法是由Haim Kaplan、Ron Shamir與Robert E. Tarjan所提出，簡稱KST演算法。主要用來找出從一個基因組到另一個基因組的最小反轉距離。有效率的計算兩個基因組間的反轉距離對於多重基因組重排問題之研究是基本且重要的。

Recently years, Computational Biology has become a new study field for computer science. The progress in genome scale sequencing and comparative mapping becomes a challenges topic in researches of genome rearrangements. Although the genome rearrangement problem of pair wise is a typical one of this kind and is well studied, algorithms for reconstructing rearrangement scenarios for multiple species are in great need. In this thesis, we study the Multiple Genome Rearrangement Problem, and give a brief survey of this problem. The Multiple Genome Rearrangement Problem is to find an evolutional tree describing the most believable rearrangement scenario for multiple species. Besides, we study and implement an algorithm to compute the reversal distance for Sorting Signed Permutations by Reversals. The algorithm was developed by Haim Kaplan, Ron Shamir and Robert E. Tarjan (abbreviated to K.S.T algorithm). It is to find the minimum number of reversals it takes to get from one genome to the other. And it is essential and important to compute the reversal distance efficient for a pair of genomes for study of multiple genome rearrangement problem.

1 Introduction
1.1 Biological Background
1.2 MathematicalModels
1.3 ProblemDefinition
1.4 PreviousWork
1.5 Thesis Organization
2 Preliminaries
2.1 Breakpoint Graph
2.2 Overlap Graph
2.3 The Connected Components of the Overlap Graph
2.4 Hurdle
2.5 Fortress
3 The K.S.T Algorithm for Sorting Signed Permutation by Reversals
3.1 Clearing the Hurdles
3.2 Safe Reversal in Happy Cliques
3.2.1 Finding a Happy Clique
3.2.2 Searching the Happy Clique
3.3 The K.S.T Algorithm
3.4 The Running Time Analysis
3.5 Experimental Results
4 The Study of Multiple Genome Rearrangement Problems
4.1 Breakpoint Analysis Method
4.2 Grid Search Algorithm
4.3 Nearest Path Search Algorithm
4.4 Greedy Split Algorithm
4.5 EG-Graph Method
4.6 Neighbor-Perturbing Algorithm
4.7 Branch-and-Bound Algorithm
5 Conclusion

[1] H. Kaplan, R. Shamir, and R.E. Tarjan, A faster and simpler algorithm for sorting signed permutations by reversals, SIAM Journal of Computing, 29(3), pp. 880 − 892, 1999.
[2] P. Berman and S. Hannenhalli, Fast Sorting by Reversal, In D.S. Hirschberg and E.W. My-ers, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, pp. 168−185, Laguna Beach, CA, 1996. Lecture Notes in Computer Science, 1075, Springer-Verlag Publishers.
[3] D. Bader, B. Moret, and M. Yan, A linear-time algorithm for computing inversion distances between signed permutations with an experimental study, J. Comput. Biol., 8(5), pp. 483 − 491, 2001.
[4] S. Hannenhalli and P. Pevzner, Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals), In Proceedings of the 27th Annual Symposium on Theory of Computing (STOC95), pp. 178 − 189, Las Vegas, NV, ACM Press, 1995.
[5] V. Bafna and P. Pevzner, Genome rearrangements and sorting by reversals, SIAM Journal on Computing, 25(2), pp. 272 − 289, 1996.
[6] A. Caprara, Sorting by reversals is difficult, In Proceedings of the 1st Conference on Computational Molecular Biology (RECOMB97), pp. 75 − 83, Santa Fe, NM, ACM Press, 1997.
[7] S. Wu and X. Gu, Algorithms for multiple genome rearrangement by signed reversals,Pacific Symposium on Biocomputing, 8, pp. 363 − 374, 2003.
[8] J. Kececioglu and D. Sankoff, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica, 13(1/2), pp. 180 − 210, 1995.
[9] D. Christie, A 3/2-approximation algorithm for sorting by reversals, In Proceedings of the 9th Annual Symposium on Discrete Algorithms (SODA 98), pp. 244 − 252, ACM Press, 1998.
[10] P. Berman, S. Hannenhalli, and M. Karpinki, 1.375-approximation algorithm for sorting by reversals, Electronic Colloquium for Computational Complexity, TR01 − 047, 2001.
[11] P. Berman and M. Karpinski, On some tighter inapproximability results, In Proceedings of the 26th ICALP, 1999, Springer-Verlag Publishers.
[12] D. Sankoff and M. Blanchette, Multiple genome rearrangement and breakpoint phylogeny, Journal of Computational Biology, 5(3), pp. 555 − 570, 1998.
[13] D. Sankoff, G. Sundaram, and J.Kececioglu, Steiner points in the space of genome rearrangements, International Journal of Foundations of Computer Science, 7, pp. 1 − 9, 1996.
[14] S. Wu and X. Gu, Multiple Genome Rearrangement By Reversals, Pacific
Symposium on Biocomputing, 7, pp. 259 − 270, 2002.
[15] G. Bourque and P. Pevzner, Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species, Genome Research, 12(1), pp. 26− 36, 2002.
[16] D. Korkin and L. Golefarb Multiple genome rearrangement: a general approach via the evolutionary genome graph, BIOINFORMATICS, 18, pp. s303 − s311, 2002.
[17] J. Kececioglu and D. Sankoff, Exact and approximation algorithms for the inversion distance between two chromosomes, Lecture Notes in Computer Science, 684, pp. 87 − 105, 1993.
[18] V. Bafna and P. Pevzner, Sorting by transpositions, In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 614 −623, 1995.
[19] DA. Christie, Sorting permutations by block-interchanges, Information Processing Letters, 60, pp. 165 − 169, 1996.
[20] M. E. Walter, Z, Dias, and J. Meidanis, Reversal and transposition distance of linear chromosomes, In String Proceeding and Information RetrievalGA South American Symposium (SPRIE 98), 1998.
[21] J. Kececioglu, and R.Ravi, Of mice and men. Evolutionary distance between genomes under translocation, In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 60, pp. 165−169, 1995.