(3.238.186.43) 您好!臺灣時間:2021/03/05 22:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蘇偉順
研究生(外文):Wei-Shun Su
論文名稱:單一核甘酸多型性與單套型區塊之研究
論文名稱(外文):A Study on SNP Haplotype Blocks
指導教授:林耀鈴
指導教授(外文):Yaw-Ling Lin
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊管理學系研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:42
中文關鍵詞:單套型區塊選擇資料遺失單一核甘酸多型性演算法多樣性
外文關鍵詞:SNPalgorithmmissing datahaplotype block selectionhaplotypediversity
相關次數:
  • 被引用被引用:0
  • 點閱點閱:326
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:29
  • 收藏至我的研究室書目清單書目收藏:0
由共通的單一核甘酸多型性所定義出來的全球人類DNA序列中的差異,對於疾病關聯與人類特徵的識別非常重要。最近的基因體研究發現,在主要的人口族群中,某些單套型區塊中的單一核甘酸多型性只會形成幾種不同的共通單套型樣式。並且對於尋找致病基因的關聯方法來說,單套型區塊結構的存在擁有著重要的含意。

我們的目標是在單套型資料中選擇最具有結構意義的單套型區塊。在這篇論文我們提出幾個有效的演算法並搭配不同的多樣性函數來選擇有興趣的單套型區塊。針對遺失資料處理的部份,我們在本論文中說明"最小多樣性問題"是一個NP-complete問題,且接著提出一個經驗法則演算法來解決遺失資料的問題。
Global patterns of human DNA sequence variation (haplotypes) defined by common single nucleotide polymorphisms (SNPs) have important implications for identifying disease associations and human traits. Recent genetics research reveals that SNPs within certain haplotype blocks induce only a few distinct common haplotypes in the majority of the population. The existence of haplotype block structure has serious implications for association-based methods for the mapping of disease genes.

Our ultimate goal is to select haplotype block designations that best capture the structure within the data. Here in this thesis we propose several efficient combinatorial algorithms related to selecting interesting haplotype blocks under different diversity functions that generalizes many previous results in the literatures. For dealing with missing SNP data, we show in this thesis that the "Minimum Diversity Problem" is NP-complete and propose a heuristic agorithm to deal with these sites.
Chinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . i
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . ii
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . vi


1 Introduction 1
1.1 Foreword . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motive and Purpose . . . . . . . . . . . . . . . . . . . 3
1.3 Background and Literature Review . . . . . . . . . . . . . 4
1.4 Chapter Outline . . . . . . . . . . . . . . . . . . . . . . 6

2 Method 7
2.1 Terminology Definition and Preprocess . . . . . . . . . . . . . 7
2.2 Diversity Functions . . . . . . . . . . . . . . . . . . . . 9
2.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Computing Diversities of All Blocks . . . . . . . . . . . . 10
2.3.2 Farthest-Site . . . . . . . . . . . . . . . . . . . 16
2.3.3 Haplotype Block Selection . . . . . . . . . . . . . . . 16
2.4 Dealing with Missing Data . . . . . . . . . . . . . . . . . . 19

3 Experiments 25
3.1 Experiment Method . . . . . . . . . . . . . . . . . . . 25
3.2 Experimental Results . . . . . . . . . . . . . . . . . . . . 26


4 Conclusion 29
4.1 Contributions . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Future Works . . . . . . . . . . . . . . . . . . . . . . 30

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[1] Eric C. Anderson and John Novembre. Finding haplotype block boundaries by using the minimum-description-length principle. Am. J. of Human Genetics, 73:336–354, 2003.
[2] D. Clayton. Choosing a set of haplotype tagging SNPs from a larger set of diallelic loci. Nature Genetics, 29(2), 2001.
[3] R. Cole, M. Farach, R. Hariharan, T. Przytycka, and M. Thorup. An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal on Computing, 30(5):1385–1404, 2002.
[4] M. Daly, J. Rioux, S. Schafiner, T. Hudson, and E. Lander. High reolution haplotype structure in the human genome. Nature Genetics, 29:229–232, 2001.
[5] E. Dawson, G. Abecasis, et al. A first-generation linkage disequilibrium map of human chromosome 22. Nature, 418:544–548, 2002.
[6] S. B. Gabriel, S. F. Schaffner, H. Nguyen, et al. The structure of haplotype blocks in the human genome. Science, 296(5576):2225–2229, 2002.
[7] M.R. Garey and D.S. Johnson. Computers and Intractability–A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
[8] G. Greenspan and D. Geiger. Model-based inference of haplotype block variation. In Seventh Annual International Conference on Computational Molecular Biology (RECOMB), 2003.
[9] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
[10] D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984.
[11] L. Helmuth. Genome research: Map of the human genome 3.0. Science, 293(5530):583–585, 2001.
[12] R. R. Hudson and N. L. Kaplan. Statistical properties of the number of recombination events in the history of a sample of dna sequences. Genetics, 111:147–164, 1985.
[13] M. Koivisto, M. Perola, R. Varilo, W. Hennah, J. Ekelund, M. Lukk, L. Peltonen, E. Ukkonen, and H. Mannila. An mdl method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. In 8th Pacific Symposium on Biocomputing (PSB), pages 502–513, 2003.
[14] W.H. Li and D. Graur. Fundamentals of Molecular Evolution. Sinauer Associates, Inc, 1991.
[15] N. Patil, A. J. Berno, D. A. Hinds, et al. Blocks of limited haplotype diversity revealed by high resolution scanning of human chromosome 21. Science, 294:1719–1723, 2001.
[16] Russell Schwartz, Andrew G. Clark, and Sorin Istrail. Methods for inferring block-wise ancestral history from haploid sequences. In WABI, pages 44–59, 2002.
[17] Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995.
[18] P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80–82, 1977.
[19] J.D. Wall and J.K Pritchard. Haplotype blocks and linkage disequilib- rium in the human genome. Nature Reviews Genetics, 4(8):587–597, 2003.
[20] N. Wang, J.M. Akey, K. Zhang, R. Chakraborty, and L. Jin. Distribution of recombination crossovers and the origin of haplotype blocks: the interplay of population history, recombination, and mutation. Am. J. Human Genetics, 71:1227–1234, 2002.
[21] K. Zhang, M. Deng, T. Chen, M.S. Waterman, and F. Sun. A dynamic programming algorithm for haplotype block partitioning. In The Na- tional Academy of Sciences, volume 99, pages 7335–7339, 2002.
[22] K. Zhang, Z.S. Qin, J.S. Liu, T. Chen T, M.S. Waterman, and F. Sun. Haplotype block partitioning and tag snp selection using genotype data and their applications to association studies. Genome Res., 14(5):908–916, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔