Wong, Ka Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 109-121). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgements --- p.iv / List of Figures --- p.ix / List of Tables --- p.xi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Objective --- p.2 / Chapter 1.3 --- Methodology --- p.2 / Chapter 1.4 --- Bioinforrnatics --- p.2 / Chapter 1.5 --- Computational Methods --- p.3 / Chapter 1.5.1 --- Evolutionary Algorithms --- p.3 / Chapter 1.5.2 --- Data Mining for TF-TFBS bindings --- p.4 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Gene Transcription --- p.5 / Chapter 2.1.1 --- Protein-DNA Binding --- p.6 / Chapter 2.1.2 --- Existing Methods --- p.6 / Chapter 2.1.3 --- Related Databases --- p.8 / Chapter 2.1.3.1 --- TRANSFAC - Experimentally Determined Database --- p.8 / Chapter 2.1.3.2 --- cisRED - Computational Determined Database --- p.9 / Chapter 2.1.3.3 --- ORegAnno - Community Driven Database --- p.10 / Chapter 2.2 --- Evolutionary Algorithms --- p.13 / Chapter 2.2.1 --- Representation --- p.15 / Chapter 2.2.2 --- Parent Selection --- p.16 / Chapter 2.2.3 --- Crossover Operators --- p.17 / Chapter 2.2.4 --- Mutation Operators --- p.18 / Chapter 2.2.5 --- Survival Selection --- p.19 / Chapter 2.2.6 --- Termination Condition --- p.19 / Chapter 2.2.7 --- Discussion --- p.19 / Chapter 2.2.8 --- Examples --- p.19 / Chapter 2.2.8.1 --- Genetic Algorithm --- p.20 / Chapter 2.2.8.2 --- Genetic Programming --- p.21 / Chapter 2.2.8.3 --- Differential Evolution --- p.21 / Chapter 2.2.8.4 --- Evolution Strategy --- p.22 / Chapter 2.2.8.5 --- Swarm Intelligence --- p.23 / Chapter 2.3 --- Association Rule Mining --- p.24 / Chapter 2.3.1 --- Objective --- p.24 / Chapter 2.3.2 --- Apriori Algorithm --- p.24 / Chapter 2.3.3 --- Partition Algorithm --- p.25 / Chapter 2.3.4 --- DHP --- p.25 / Chapter 2.3.5 --- Sampling --- p.25 / Chapter 2.3.6 --- Frequent Pattern Tree --- p.26 / Chapter 3 --- Discovering Protein-DNA Binding Sequence Patterns Using Associa- tion Rule Mining --- p.27 / Chapter 3.1 --- Materials and Methods --- p.28 / Chapter 3.1.1 --- Association Rule Mining and Apriori Algorithm --- p.29 / Chapter 3.1.2 --- Discovering associated TF-TFBS sequence patterns --- p.29 / Chapter 3.1.3 --- "Data, Preparation" --- p.31 / Chapter 3.2 --- Results and Analysis --- p.34 / Chapter 3.2.1 --- Rules Discovered --- p.34 / Chapter 3.2.2 --- Quantitative Analysis --- p.36 / Chapter 3.2.3 --- Annotation Analysis --- p.37 / Chapter 3.2.4 --- Empirical Analysis --- p.37 / Chapter 3.2.5 --- Experimental Analysis --- p.38 / Chapter 3.3 --- Verifications --- p.41 / Chapter 3.3.1 --- Verification by PDB --- p.41 / Chapter 3.3.2 --- Verification by Homology Modeling --- p.45 / Chapter 3.3.3 --- Verification by Random Analysis --- p.45 / Chapter 3.4 --- Discussion --- p.49 / Chapter 4 --- Designing Evolutionary Algorithms for Multimodal Optimization --- p.50 / Chapter 4.1 --- Introduction --- p.50 / Chapter 4.2 --- Problem Definition --- p.51 / Chapter 4.2.1 --- Minimization --- p.51 / Chapter 4.2.2 --- Maximization --- p.51 / Chapter 4.3 --- An Evolutionary Algorithm with Species-specific Explosion for Multi- modal Optimization --- p.52 / Chapter 4.3.1 --- Background --- p.52 / Chapter 4.3.1.1 --- Species Conserving Genetic Algorithm --- p.52 / Chapter 4.3.2 --- Evolutionary Algorithm with Species-specific Explosion --- p.53 / Chapter 4.3.2.1 --- Species Identification --- p.53 / Chapter 4.3.2.2 --- Species Seed Delta Evaluation --- p.55 / Chapter 4.3.2.3 --- Stage Switching Condition --- p.56 / Chapter 4.3.2.4 --- Species-specific Explosion --- p.57 / Chapter 4.3.2.5 --- Calculate Explosion Weights --- p.59 / Chapter 4.3.3 --- Experiments --- p.59 / Chapter 4.3.3.1 --- Performance measurement --- p.60 / Chapter 4.3.3.2 --- Parameter settings --- p.61 / Chapter 4.3.3.3 --- Results --- p.61 / Chapter 4.3.4 --- Conclusion --- p.62 / Chapter 4.4 --- A. Crowding Genetic. Algorithm with Spatial Locality for Multimodal Op- timization --- p.64 / Chapter 4.4.1 --- Background --- p.64 / Chapter 4.4.1.1 --- Crowding Genetic Algorithm --- p.64 / Chapter 4.4.1.2 --- Locality of Reference --- p.64 / Chapter 4.4.2 --- Crowding Genetic Algorithm with Spatial Locality --- p.65 / Chapter 4.4.2.1 --- Motivation --- p.65 / Chapter 4.4.2.2 --- Offspring generation with spatial locality --- p.65 / Chapter 4.4.3 --- Experiments --- p.67 / Chapter 4.4.3.1 --- Performance measurements --- p.67 / Chapter 4.4.3.2 --- Parameter setting --- p.68 / Chapter 4.4.3.3 --- Results --- p.68 / Chapter 4.4.4 --- Conclusion --- p.68 / Chapter 5 --- Generalizing Protein-DNA Binding Sequence Representations and Learn- ing using an Evolutionary Algorithm for Multimodal Optimization --- p.70 / Chapter 5.1 --- Introduction and Background --- p.70 / Chapter 5.2 --- Problem Definition --- p.72 / Chapter 5.3 --- Crowding Genetic Algorithm with Spatial Locality --- p.72 / Chapter 5.3.1 --- Representation --- p.72 / Chapter 5.3.2 --- Crossover Operators --- p.73 / Chapter 5.3.3 --- Mutation Operators --- p.73 / Chapter 5.3.4 --- Fitness Function --- p.74 / Chapter 5.3.5 --- Distance Metric --- p.76 / Chapter 5.4 --- Experiments --- p.77 / Chapter 5.4.1 --- Parameter Setting --- p.77 / Chapter 5.4.2 --- Search Space Estimation --- p.78 / Chapter 5.4.3 --- Experimental Procedure --- p.78 / Chapter 5.4.4 --- Results and Analysis --- p.79 / Chapter 5.4.4.1 --- Generalization Analysis --- p.79 / Chapter 5.4.4.2 --- Verification By PDB --- p.86 / Chapter 5.5 --- Conclusion --- p.87 / Chapter 6 --- Predicting Protein Structures on a Lattice Model using an Evolution- ary Algorithm for Multimodal Optimization --- p.88 / Chapter 6.1 --- Introduction --- p.88 / Chapter 6.2 --- Problem Definition --- p.89 / Chapter 6.3 --- Representation --- p.90 / Chapter 6.4 --- Related Works --- p.91 / Chapter 6.5 --- Crowding Genetic Algorithm with Spatial Locality --- p.92 / Chapter 6.5.1 --- Motivation --- p.92 / Chapter 6.5.2 --- Customization --- p.92 / Chapter 6.5.2.1 --- Distance metrics --- p.92 / Chapter 6.5.2.2 --- Handling infeasible conformations --- p.93 / Chapter 6.6 --- Experiments --- p.94 / Chapter 6.6.1 --- Performance Metrics --- p.94 / Chapter 6.6.2 --- Parameter Settings --- p.94 / Chapter 6.6.3 --- Results --- p.94 / Chapter 6.7 --- Conclusion --- p.95 / Chapter 7 --- Conclusion and Future Work --- p.97 / Chapter 7.1 --- Thesis Contribution --- p.97 / Chapter 7.2 --- Fixture Work --- p.98 / Chapter A --- Appendix --- p.99 / Chapter A.1 --- Problem Definition in Chapter 3 --- p.107 / Bibliography --- p.109 / Author's Publications --- p.122