跳到主要內容

臺灣博碩士論文加值系統

(44.192.20.240) 您好!臺灣時間:2024/02/27 12:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊力穎
研究生(外文):Lee-in Yang
論文名稱:對於RMP問題,一個有效率的分支與限制演算法
論文名稱(外文):An Efficient Algorithm for Reversal Median Problem
指導教授:張貿翔張貿翔引用關係
指導教授(外文):Maw-Shang Chang
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:95
語文別:英文
論文頁數:62
中文關鍵詞:反轉中值問題
外文關鍵詞:ReversalMedian Problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:267
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
分支與限制的演算法是以列出所有可能解的方式,逐一篩選出正確的答案。因此,當篩選的方式愈有效率,演算法的效率也相對愈高。在生物計算的領域中,尋找Median的問題,是在於找出與其他所有基因組間的演化路徑的距離總和最短的一個基因組。RMP是Reversal Median Problem的縮寫,是在生物計算領域中,尋找Median的問題,而其演化路徑的距離是定義於reversal 距離;在[3]中,已經證明這是一個NP-hard的問題。在目前所知的一些尋找Median的問題中,所定義的演化路徑距離,如reversal 距離,cycle 距離[3],breakpoint 距離等,都有一個共同的特性,稱做三角不等式。在[10]中,Adam C. Sipel提出一個分支與限制的演算法,以解決尋找Median的問題。在這篇論文中,我們利用演化路徑的特性,發展出一個對尋找Median的問題的篩選方式。我們將改進過的演算法,與先前的演算法,以及目前最有效率的Alberto Caprara [3] 的演算法比較;由實驗數據顯示,我們的演算法效能優於他們的演算法。Adam C. Sipel和Alberto Caprara 的演算法已經在套裝軟體: GRAPPA [6] 中實作並最佳化。
Branch-and-bound is a powerful approach of sequential possible-solution enumerating that has an established theoretical foundation and has proven effective in given crucial bounds. The Median Problem is the problem in computational biology that estimates the minimum evolutionary distances to transform one genome into the others. In Reversal Median Problem (RMP for short), the evolutionary distance is the minimum number of reversals to transform one to the other. This problem was shown NP-hard in computational biology [3]. Some median problems such as the Reversal Median Problem (RMP for short), the Cycle Median Problem (CMP for short) [3], the Breakpoint Median Problem (BMP for short), etc, all their evolutionary distances, such as reversal distance, cycle distance, breakpoint distance, respectively satisfy the metric property, naming triangle inequality. Adam C. Sipel proposed a branch-and-bound algorithm that solves the RMP to optimality [10]. In this thesis, we propose a technique for speeding the median problems that satisfy the metric property and successfully apply it to the branch-and-bound algorithm. Experimental results show that our improved branch-and-bound algorithm outperform the previous one and even the most efficient approach by Alberto Caprara [3] in GRAPPA[6].
List of Figures V
List of Tables VI
List of Algorithms & Functions VII


1 Introduction 1
1.1 Motivation. ---------------------------------------------------- 1
1.2 The Genomic Distance. ------------------------------------------ 1
1.2.1 Basic Rearrangements Between Chromosomes ---------------- 3
1.2.2 Fission and Fusion -------------------------------------- 4
1.2.3 Micro-Rearrangements and Macro-Rearrangements ----------- 5
1.2.4 Breakpoints and Reversals ------------------------------- 5
1.3 The Reversal Median Problem. ----------------------------------- 6

2 A Branch-and-Bound Algorithm and Possible Improvement 8
2.1 B&B - terminology and general description. -------------------- 8
2.2 A B&B Algorithm. ---------------------------------------------- 10
2.3 The Possible Improvement. ------------------------------------- 13

3 Preliminary 14

4 Estimate for Distance between Median and All Given Permutations 16
4.1 Distances Between Median and Three Given Permutations. ------------ 16
4.2 Lower Bounds. ----------------------------------------------------- 17
4.3 Upper Bounds. ----------------------------------------------------- 18
4.4 Conclusion. ------------------------------------------------------- 20

5 An Efficient Algorithm for Reversal Median Problem with Three Permutations 21
5.1 Branching Methods. ------------------------------------------------ 22
5.2 Bounding Functions. ----------------------------------------------- 22
5.2.1 The Upper Bounds and Lower Bounds for Median Score --------- 23
5.3 Pruning Methods. -------------------------------------------------- 24
5.3.1 Pruning 1 ------------------------------------------------- 24
5.3.2 Pruning 2 ------------------------------------------------- 25
5.4 The Efficient Implement. ------------------------------------------ 29
5.5 Experimental Methods & Results. ----------------------------------- 33
5.5.1 Compare The Average Branched Nodes ------------------------- 33
5.5.2 Compare The Average Time to Find The Median ---------------- 42
5.6 Conclusion. ------------------------------------------------------- 45

References 46

Appendix 48
Appendix A: 49
The Upper Bounds and Lower Bounds for Distances Between Median and Three Given Permutations
[1] D.A. Bader, Bernard M. E. Moret and M. Yan: “A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study”, Algorithms and Data Structures: Seventh International Workshop, WADS 2001,Brown University, Providence, RI, August 8-10, 2001, Proceedings (F. Dehne, J.-R. Sack, and R. Tamassia, eds.), Lecture Notes in Computer Science, vol. 2125, 2001, pp. 365-376.

[2] Alberto Caprara: "Sorting by reversals is difficult", Proceedings of the 1st Annual International Conference on Research in Computational Molecular Biology (RECOMB 1997) (S.Istrail, P.A. Pevzner, and M.S. Waterman, eds.), 1997, pp. 75-83.

[3] Alberto Caprara: “The Reversal Median Problem“, INFORMS Journal in Computing , 2003, 15(1):pp 93-113.

[4] J. Clausen and M. Perregaard, “On the Best Search Strategy in Parallel Branch-and-Bound - Best-First-Search vs. Lazy Depth-First-Search“, Proceedings of POC96 (1996), also DIKU Report 96/14, 11 p.

[5] Adam C. Siepel and Bernard M. E. Moret: “Finding an Optimal Inversion Median Experimental Results”, Proceedings of the 1st International Workshop on Algorithms in Bioinformatics, WABI 2001, Lecture Notes in Computer Science, vol. 2149, 2001, pp. 189-203.

[6] J, Tang, Bernard M.E. Moret, Adam C. Siepel, Alberto Caprara, D.A. Bader, T. Warnow, S.K. Wyman and M.Yan: “GRAPPA: Genome Rearrangement Analysis under Parsimony and other Phylogenetic Algorithm”, the University of New Mexico and the University of Texas at Austin, 2.0 edition, 2004.
Available at http://www.cs.unm.edu/moret/GRAPPA/.

[7] Pavel A. Pevzner and Tesler G :“Genome rearrangements in mammalian evolution: lessons from human and mouse genomes”, Genome Res 13: 37–45, 2003.

[8] G.A. Watterson, W.J. Ewens, and T.E. Hallt: “The Chromosome Inversion Problem”, Journal of Theoretical Biology 99, 1-7,1982.

[9] Pavel A. Pevzner: “Computational Molecular Biology”, MIT press, chapter 10,2000

[10] Adam C. Siepel: “Exact Algorithm for The Reversal Median Problem”, Master’s thesis, the University of New Mexico, Albuquerque, New Mexico, Dec 2001

[11] Sheng Yao. Su: “An Exact Algorithm for The Reversal Median Problem”, Master’s thesis, the University of Chung Cheng, Chia Yi, Taiwan, R.O.C, July 2005
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文