# 臺灣博碩士論文加值系統

(34.204.169.230) 您好！臺灣時間：2024/02/21 22:59

:::

### 詳目顯示

:

• 被引用:0
• 點閱:278
• 評分:
• 下載:9
• 書目收藏:0
 建構演化樹是現今計算生物裡一個很重要的問題。釵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……………………………………………12.Preliminary………………………………………………53.An Algorithm for Finding an Exact Median………93.1.Bounds…………………………………………………103.2.The Upper Bound of Reversal Distance…………123.3.The Branch and Bound Algorithm…………………143.4.Implementation………………………………………174.Experimental Results…………………………………225.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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 基因組重排問題之研究

 1 2. 余德成、溫金豐、陳泰哲（2002），科技產業中領導行為與組織公民行為之關係：檢驗督導信任的情境效應，中山管理評論，10(1)，65-91。 2 2. 余德成、溫金豐、陳泰哲（2002），科技產業中領導行為與組織公民行為之關係：檢驗督導信任的情境效應，中山管理評論，10(1)，65-91。

 1 不同高能隙主體材料對白光有機發光二極體光電特性影響之研究 2 學什麼？像什麼：報紙版面設計之競爭意涵—以蘋果日報出刊前後中時聯合自由三報為例 3 論後工業脈絡下台灣遊戲產業勞動控制的彈性 4 設計與實做一個針對MPEGAudioLayer-3解碼的可客製化運算單元 5 分析利用角度為基礎演算法完成多地理區域的資料傳送 6 具鷹架教學理論框架且符合SCORM2004之教材編輯管理系統 7 利用複合環的選擇完成星狀光纖網路上有效率的多對多資料傳送 8 影響訓練移轉之因素-以壽險外勤人員為例 9 全國大專校院運動會發展與教育意涵之研究 10 EarningsManagementandtheUnderperformanceofConvertibleBondOfferings 11 Market-TimingStrategyinNIKKEI225,inFTSR100,andinDJIA 12 論JohnMcDowell的道德感知理論 13 企業經濟附加價值與平衡計分卡聯結運用之研究—以C電子公司為例 14 政風人員工作壓力、因應策略與壓力反應關係研究 15 警察機關防制詐欺犯罪之評估~以台南縣為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室