(3.230.76.48) 您好!臺灣時間:2021/04/11 08:59
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林國任
研究生(外文):Gwo-Renn Lin
論文名稱:基因組重排問題之研究
論文名稱(外文):A Study of Genome Rearrangement Problem
指導教授:張貿翔張貿翔引用關係
指導教授(外文):Maw-Shang Chang
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:50
中文關鍵詞:計算分子生物多重基因組重排反轉距離演算法
外文關鍵詞:computational molecular biologymultiple genome rearrangementreversal distancealgorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:153
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
近年來,計算生物學在資訊科學已變成一個新的研究領域。在基因組重排研究中,基因組的序列化與比較是較具挑戰性的主題。雖然在基因組重排問題中,兩個基因組的比較已被廣泛的研究,但建構多個物種間演化過程的演算法還是大量被需要的。在本論文中,我們研究多重基因組重排問題,並探討有關這個問題目前的研究。多重基因組重排問題是去找一個用來描述多個物種間演化情景的演化樹。此外,我們研究與實作一個有關有號排列反轉排序距離計算的演算法。這個演算法是由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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔