跳到主要內容

臺灣博碩士論文加值系統

(44.220.255.141) 您好!臺灣時間:2024/11/14 05:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林威廷
研究生(外文):Wei-Ting Lin
論文名稱:利用演化式演算法進行多目標標籤單核苷酸多型性之選擇
論文名稱(外文):Multi-Objective Tag SNPs Selection Using Evolutionary Algorithm
指導教授:丁川康丁川康引用關係
指導教授(外文):Chuan-Kang Ting
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:54
中文關鍵詞:演化式計算單核苷酸多型性多目標最佳化
外文關鍵詞:Single nucleotide polymorphismEvolutionary algorithmMulti-Objective optimization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:343
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
Single nucleotide polymorphism (SNP) has been widely studied in many purposes, of which most focus on selecting a small number of representative SNPs, called tag SNPs, for relative researches and haplotype identification. Since SNPs data may be unavailable from experimental error, robust tag SNPs are proposed to deal with missing SNP data. When the haplotype is long enough, it is expected that tag SNPs is capable of distinguishing some segments in the haplotype. This study formulates the tag SNPs selection problem into a multi-objective optimization problem, seeking for minimum tag SNPs, robust tag SNPs, and dissimilar haplotypes.

A famous multiple objectives evolutionary algorithm, NSGA-II, and a many objectives evolutionary algorithm, MSOPS, are adopted to address multi-objective tag SNPs selection. Moreover, this study proposes a greedy based modification for these two algorithms to improve their performance. The experimental results show that MSOPS is superior to NSGA-II for this problem, and the greedy based modification for both algorithms further enhance their search ability.

According to the integrated relations between objectives, the combination of diverse SNPs usually has lower tolerance for missing data and number of tag SNPs. This result comes from the rareness of the mutant nucleotides in a single human race, its occurrence is relatively less than wild nucleotides after natural selection.
Contents 3
List of Figures 5
List of Tables 6
1 Introduction 7
1.1 Single Nucleotide Polymorphism . . . . . . . . . . . . . . . . . . . . . 7
1.2 Existing Methods for Tag SNPs Selection . . . . . . . . . . . . . . . . 10
1.3 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Multiple Objectives . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Many Objectives . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Problem Formulation 15
2.1 Set Cover Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 New Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Proposed Methods for Tag SNPs Selection 19
3.1 Non-dominated Sorting Genetic Algorithm-II (NSGA-II) . . . . . . . . 19
3.2 Multiple Single Objective Pareto Sampling . . . . . . . . . . . . . . . . 21
3.3 Greedy Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Experimental Results 26
4.1 Settings and Presentations . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 NSGA-II vs. MSOPS . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.2 Greedy NSGA-II vs. Greedy MSOPS . . . . . . . . . . . . . . 28
4.2.3 General Relation between Objectives . . . . . . . . . . . . . . . 31
4.3 Comparison between Test Algorithms . . . . . . . . . . . . . . . . . . 34
4.4 Summary for Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Conclusions and Future Work 41
Appendix A The Experimental Results of Different Number of Weight Vectors on
MSOPS 43
Bibliography 51
[1] D. Brockhoff and E. Zitzler. Improving hypervolume-based multiobjective evolutionary
algorithms by using objective reduction methods. In 2007 IEEE Congress
on Evolutionary Computation, pages 2086–2093, 2007.
[2] C. Carlson, M. Eberle, M. Rieder, Q. Yi, L. Kruglyak, and D. Nickerson. Selecting
a maximally informative set of single-nucleotide polymorphisms for association
analyses using linkage disequilibrium. The American Journal of Human Genetics,
74(1):106–120, 2004.
[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms,
Second Edition. The MIT Press, 2nd edition, 2001.
[4] K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley,
2001.
[5] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective
genetic algorithm: NSGA-II. IEEE Trans. Evolutionary Computation, 6(2):182–
197, 2002.
[6] M. R. Garey and D. S. Johnson. Computers and intractability; a guide to the
theory of NP-completeness. W.H. Freeman, 1979.
[7] D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley, 1989.
[8] E. Halperin, G. Kimmel, and R. Shamir. Tag SNP selection in genotype data for
maximizing SNP prediction accuracy. In ISMB (Supplement of Bioinformatics),
pages 195–203, 2005.
[9] J. Hampe, S. Schreiber, and M. Krawczak. Entropy-based snp selection for genetic
association studies. Human Genetics, 114:36–43, 2003.
[10] Y. T. Huang, K. K. Zhang, T. Chen, and K. M. Chao. Selecting additional tag snps
for tolerating missing data in genotyping. BMC Bioinformatics, 6(1):263, 2005.
[11] R. M. Hubley, E. Zitzler, and J. C. Roach. Evolutionary algorithms for the selection
of single nucleotide polymorphisms. BMC Bioinformatics, 4, 2003.
[12] E. J. Hughes. Multiple Single Objective Pareto Sampling. In Proceedings of
the 2003 Congress on Evolutionary Computation (CEC’2003), volume 4, pages
2678–2684, 2003.
[13] E. J. Hughes. MSOPS-II: A general-purpose many-objective optimiser. In 2007
IEEE Congress on Evolutionary Computation (CEC’2007), pages 3944–3951,
2007.
[14] H. Ishibuchi, Y. Hitotsuyanagi, and Y. Nojima. Scalability of multiobjective genetic
local search to many-objective problems: Knapsack problem case studies.
In 2008 Congress on Evolutionary Computation (CEC’2008), pages 3587–3594,
2008.
[15] H. Ishibuchi and Y. Nojima. Optimization of Scalarizing Functions Through Evolutionary
Multiobjective Optimization. In Evolutionary Multi-Criterion Optimization,
4th International Conference, EMO 2007, pages 51–65, 2007.
[16] H. Ishibuchi, N. Tsukamoto, Y. Hitotsuyanagi, and Y. Nojima. Effectiveness
of scalability improvement attempts on the performance of NSGA-II for manyobjective
problems. In GECCO ’08: Proceedings of the 10th annual conference
on Genetic and evolutionary computation, pages 649–656, 2008.
[17] H. Ishibuchi, N. Tsukamoto, and Y. Nojima. Iterative approach to indicator-based
multiobjective optimization. In 2007 IEEE Congress on Evolutionary Computation,
pages 3967–3974, 2007.
[18] H. Ishibuchi, N. Tsukamoto, and Y. Nojima. Evolutionary many-objective optimization:
A short review. In 2008 IEEE World Congress on Computational
Intelligence, 2008.
[19] A. Jaszkiewicz. On the Computational Efficiency of Multiple Objective Metaheuristics.
The Knapsack Problem Case Study. European Journal of Operational
Research, 158(2):418–433, 2004.
[20] S. Kukkonen and J. Lampinen. Ranking-dominance and many-objective optimization.
In 2007 IEEE Congress on Evolutionary Computation (CEC’2007), pages
3983–3990, 2007.
[21] W. Liu, W. Zhao, and G. A. Chase. The impact of missing and erroneous genotypes
on tagging snp selection and power of subsequent association tests. Hum
Hered, 61:31–44, 2006.
[22] Z. Liu, S. Lin, and M. Tan. Genome-wide tagging SNPs with entropy-based monte
carlo method. Journal of Computational Biology, 13(9):1606–1614, 2006.
[23] N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting
in genetic algorithms. Evolutionary Computation, 2:221–248, 1994.
[24] D. O. Stram. Tag snp selection for association studies. Genet Epidemiol,
27(4):365–374, 2004.
[25] T. Wagner, N. Beume, and B. Naujoks. Pareto-, Aggregation-, and Indicator-
Based Methods in Many-Objective Optimization. In Evolutionary Multi-Criterion
Optimization, 4th International Conference, EMO 2007, pages 742–756, 2007.
[26] L. S. Wang and Y. Xu. Haplotype inference by maximum parsimony. Bioinformatics,
19(14):1773–1780, 2003.
[27] K. Zhang, Z. S. Qin, J. S. Liu, T. Chen, M. S. Waterman, and F. Sun. Haplotype
block partitioning and tag snp selection using genotype data and their applications
to association studies. Genome Research, 14(5):908–916, 2004.
[28] J. H. Zhao, S. Lissarrague, L. Essioux, and P. C. Sham. Genecounting: haplotype
analysis with missing genotypes. Bioinformatics, 18(12):1694–1695, 2002.
[29] E. Zitzler and S. Künzli. Indicator-based Selection in Multiobjective Search. In
Parallel Problem Solving from Nature - PPSN VIII, pages 832–842, 2004.
[30] E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength pareto
evolutionary algorithm for multiobjective optimization. In K. Giannakoglou,
D. Tsahalis, J. Periaux, K. Papailiou, and T. Fogarty, editors, Evolutionary Methods
for Design, Optimisation and Control, Barcelona, Spain, 2002. CIMNE.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊