臺灣博碩士論文加值系統

單核苷酸多型體在各種分析應用，包括醫療診斷和藥物設計中扮演了重要角色。它們包含了最高分辨率的基因指紋識別來關聯疾病與人類特徵。單倍體，由單核苷酸多型體組成，因連鎖遺傳變異，鄰近區段常常一併被繼承下來。最近，遺傳學研究表明，特定的單倍型區塊誘使出只有幾種常見的單體型，在主要的人類族群中。單倍型塊的討論基於疾病基因的關聯與定位方法上有重大的影響。
我們提出的方法，調查了許多以前的文獻中相關的一些有效的組合算法，去根據不同的多樣性算式，選擇感興趣的單倍型塊。然而，這些方法計算相當耗時。本論文採用的方法，使用MapReduce去平行化和管理其程式執行。實驗結果表明，原始的單執行序程式經過了map/reduce平行，將現有的HapMap的資料庫獲得的數據做分析，計算的效率將以所使用的處理器數目成比例的成長，可以有效地提高計算效能。

SNPs play important roles for various analysis applications including medical diagnostic and drug design. They contain the highest-resolution genetic fingerprint for identifying disease associations and human features. Haplotype, is composed of SNPs, region of linked genetic variants that are neighboring usually inherited together. Recently, genetics researches show that SNPs within certain haplotype blocks induce only a few distinct common haplotypes in the majority of the population. The discussion of haplotype block has serious implications of method with association-based for the disease genes mapping.
We proposed the method in investigating several efficient combinatorial algorithms related to selecting interesting haplotype blocks under different diversity functions that generalizes many previous results in the literatures. However, the proposed method is computation-consuming. This thesis adopts approach using the MapReduce paradigm to parallelize tools and manage their execution. The experiment shows that the map/reduce-paralleled from the original sequential combinatorial algorithm performs well on the real-world data obtained in from the HapMap data set; the computation efficiency can be effectively improved proportional to the number of processors being used.

ACKNOWLEDGE I
CHINESE ABSTRACT II
ABSTRACT IV
CONTENTS VI
FIGURES VII
CHAPTER 1 INTRODUCTION 1
1.1 SNPs to Haplotypes 1
1.2 Motivation and Purpose 5
1.3 Hadoop and MapReduce 8
CHAPTER 2 RELATED WORKS 10
2.1 Different Measurement for Haplotype partitioning 10
2.2 Common Haplotype 12
2.3 Monotonic Diversity 14
2.4 Hadoop MapReduce framework 16
CHAPTER 3 ALGORITHMS FOR LONGEST BLOCKS PARTITIONING USING K BLOCKS OF TAGSNPS 19
3.1 The Preprocessing 19
3.2 Dynamic Programming Algorithms 20
3.3 TagSNPs Selection 22
CHAPTER 4 USING MAPREDUCE FRAMEWORK TO COMPUTE BLOCK DIVERSITY IN PARALLEL 24
4.1 The Preprocessing 24
4.2 Divide work 25
4.3 Parallel work 27
CHAPTER 5 EXPERIMENTS 29
5.1 Experimental environment and data source 29
5.2 Implement 30
5.3 Experimental results 31
CHAPTER 6 CONCLUSION 34
6.1 Conclusion 34
6.2 Future work 35
REFERENCE 36
APPENDIX A 40

International HapMap Project. http://www.hapmap.org/index.html.en.
J. Craig Venter, Mark D. Adams, Eugene W. Myers, et al. The Sequence of the Human Genome. Science, 291(5507):1304–1351, 2001.
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.
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.
M. J. Daly, J. D. Rioux, S. F. Scha?ner, T. J. Hudson, and E. S. Lander. High-resolution haplotype structure in the human genome. Nature Genetics, 29:229–232, 2001.
M. Olivier, V. I. Bustos, M. R. Levy, et al. Complex High-Resolution Linkage Disequilibrium and Haplotype Patterns of Single-Nucleotide Polymorphisms in 2.5 Mb of Sequence on Human Chromosome 21. Genomics, 78, Nov.
Russell Schwartz, Andrew G. Clark, and Sorin Istrail. Methods for Inferring Block-Wise Ancestral History from Haploid Sequences. In WABI, pages 44–59, 2002.
G. C. Johnson, L. Esposito, B. J. Barratt, et al. Haplotype tagging for the identification of common disease genes. Nat Genet., 29(2):233 – 7, Oct 2001.
K. Zhang, M. Deng, T. Chen, M.S. Waterman, and F. Sun. A dynamic programming algorithm for haplotype block partitioning. In The National Academy of Sciences, volume 99, pages 7335–7339, 2002.
J. D. Rioux, M. J. Daly, M. S. Silverberg, K. Lindblad, H. Steinhart, Z. Cohen, et al. Genetic variation in the 5q31 cytokine gene cluster confers susceptibility to Crohn disease. Nature Genetics, 29:223–228, 2001.
Hadoop - Apache Software foundation project home page [http://hadoop.apache.org/]
Taylor, R.C., 2010, An overview of the Hadoop/MapReduce/HBase framework and its current applications in bioinformatics. BMC Bioinformatics, 11:S1.
Dean, J., Ghemawat, S., 2010, MapReduce: A Flexible Data Processing Tool. Communications of the ACM, 53, 72-77.
Schatz, M., 2009, Cloudburst: Cloudburst: highly sensitive read mapping with MapReduce. Bioinformatics, 25, 1363-1369.
D. Clayton. Choosing a set of haplotype tagging SNPs from a larger set of diallelic loci. Nature Genetics, 29(2), 2001.
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.
J.D. Wall and J.K Pritchard. Haplotype blocks and linkage disequilibrium in the human genome. Nature Reviews Genetics, 4(8):587–597, 2003.
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.
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.
M. Nordborg and S. Tavare. Linkage disequilibrium: what history has to tell us. Trends in Genetics, 18, Feb.
R. C. Lewontin. THE INTERACTION OF SELECTION AND LINKAGE. I. GENERAL CONSIDERATIONS; HETEROTIC MODELS. Genetics, 49(1):49–67, 1964.
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.
M. Koivisto, M. Perola, R. Varilo, W. Hennah, J. Ekelund, M. Lukk, L. Peltonen, E. Ukkonen, and H. Mannila. An MDL method for ?nding haplotype blocks and for estimating the strength of haplotype block boundaries. In 8th Pacific Symposium on Biocomputing (PSB), pages 502–513, 2003.
G. Greenspan and D. Geiger. Model-based inference of haplotype block variation. In Seventh Annual International Conference on Computational Molecular Biology (RECOMB), 2003.
W.H. Li and D. Graur. Fundamentals of Molecular Evolution. Sinauer Associates, Inc, 1991.
Yaw-Ling Lin, Guan-Jie Hua, Wen-Pei Chen. Block Partition and Tag Selection in Human SNP Haplotype. Computer Society of the Republic of China, 21(3), 59-69, 2010.
D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
Esko Ukkonen. On-Line Construction of Su?x Trees. Algorithmica, 14(3):249–260, 1995.
D. Harel and R. E. Tarjan. Fast algorithms for ?nding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984.
Wei-Shun Su. A Study on SNP Haplotype Blocks. Master’s thesis, Providence University, Jun 2006.
Chapman, J.M., Cooper, J.D., Todd, J.A., Clayton, D.G., 2003, Detecting disease associations due to linkage disequilibrium using haplotype tags: a class of tests and the determinants of statistical power. Hum. Hered., 56, 18-31.
C. L. Hung, Y. L. Lin, G. J. Hua, Y. C. Hu, “CloudTSS: A TagSNP Selection Approach on Cloud Computing,” Grid and Distributed Computing, Communications in Computer and Information Science, (T. H. Kim et. Al., Eds.), Springer-Verlag, Vol. 261, pp. 525-534, 2011. [EI]