The tremendous increase in biological sequence data presents us with an opportunity to understand the molecular and cellular basis for cellular life. Comparative studies of these sequences have the potential, when applied with sufficient rigor, to decipher the structure, function, and evolution of cellular components. The accuracy and detail of these studies are directly proportional to the quality of these sequences alignments. Given the large number of sequences per family of interest, and the increasing number of families to study, improving the speed, accuracy and scalability of MSA is becoming an increasingly important task. In the past, much of interest has been on Global MSA. In recent years, the focus for MSA has shifted from global MSA to local MSA. Local MSA is being needed to align variable sequences from different families/species. In this dissertation, we developed two new algorithms for fast and scalable local MSA, a three-way-consistency-based MSA and a biclustering -based MSA. The first MSA algorithm is a three-way-Consistency-Based MSA (CBMSA). CBMSA applies alignment consistency heuristics in the form of a new three-way alignment to MSA. While three-way consistency approach is able to maintain the same time complexity as the traditional pairwise consistency approach, it provides more reliable consistency information and better alignment quality. We quantify the benefit of using three-way consistency as compared to pairwise consistency. We have also compared CBMSA to a suite of leading MSA programs and CBMSA consistently performs favorably. We also developed another new MSA algorithm, a biclustering-based MSA. Biclustering is a clustering method that simultaneously clusters both the domain and range of a relation. A challenge in MSA is that the alignment of sequences is often intended to reveal groups of conserved functional subsequences. Simultaneously, the grouping of the sequences can impact the alignment; precisely the kind of dual situation biclustering algorithms are intended to address. We define a representation of the MSA problem enabling the application of biclustering algorithms. We develop a computer program for local MSA, BlockMSA, that combines biclustering with divide-and-conquer. BlockMSA simultaneously finds groups of similar sequences and locally aligns subsequences within them. Further alignment is accomplished by dividing both the set of sequences and their contents. The net result is both a multiple sequence alignment and a hierarchical clustering of the sequences. BlockMSA was compared with a suite of leading MSA programs. With respect to quantitative measures of MSA, BlockMSA scores comparable to or better than the other leading MSA programs. With respect to biological validation of MSA, the other leading MSA programs lag BlockMSA in their ability to identify the most highly conserved regions.

Tse, Sui Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 95-104). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.1.1 --- Basic Concepts and Definitions --- p.2 / Chapter 1.2 --- Evolutionary Algorithms --- p.5 / Chapter 1.2.1 --- Chromosome Encoding --- p.6 / Chapter 1.2.2 --- Selection --- p.7 / Chapter 1.2.3 --- Crossover --- p.9 / Chapter 1.2.4 --- Mutation --- p.10 / Chapter 1.2.5 --- Elitism --- p.11 / Chapter 1.2.6 --- Niching --- p.11 / Chapter 1.2.7 --- Population Manipulation --- p.13 / Chapter 1.2.8 --- Building Blocks --- p.13 / Chapter 1.2.9 --- Termination Conditions --- p.14 / Chapter 1.2.10 --- Co-evolution --- p.14 / Chapter 1.3 --- Local Search --- p.15 / Chapter 1.4 --- Memetic Algorithms --- p.16 / Chapter 1.5 --- Objective --- p.17 / Chapter 1.6 --- Summary --- p.17 / Chapter 2 --- Background --- p.18 / Chapter 2.1 --- Multiple Drugs Tumor Chemotherapy --- p.18 / Chapter 2.2 --- Bioinformatics --- p.22 / Chapter 2.2.1 --- Basics of Bioinformatics --- p.24 / Chapter 2.2.2 --- Applications on Biomedical Systems --- p.26 / Chapter 3 --- A New Drug Administration Dynamic Model --- p.29 / Chapter 3.1 --- Three Drugs Mathematical Model --- p.31 / Chapter 3.1.1 --- Rate of Change of Different Subpopulations --- p.32 / Chapter 3.1.2 --- Rate of Change of Different Drug Concen- trations --- p.35 / Chapter 3.1.3 --- Toxicity Effects --- p.35 / Chapter 3.1.4 --- Summary --- p.36 / Chapter 4 --- Memetic Algorithm - Iterative Dynamic Program- ming (MA-IDP) --- p.38 / Chapter 4.1 --- Problem Formulation: Optimal Control Problem (OCP) for Mutlidrug Optimization --- p.38 / Chapter 4.2 --- Proposed Memetic Optimization Algorithm --- p.40 / Chapter 4.2.1 --- Iterative Dynamic Programming (IDP) . . --- p.40 / Chapter 4.2.2 --- Adaptive Elitist-population-based Genetic Algorithm (AEGA) --- p.44 / Chapter 4.2.3 --- Memetic Algorithm 一 Iterative Dynamic Programming (MA-IDP) --- p.50 / Chapter 4.3 --- Summary --- p.56 / Chapter 5 --- MA-IDP: Experiments and Results --- p.57 / Chapter 5.1 --- Experiment Settings --- p.57 / Chapter 5.2 --- Optimization Results --- p.61 / Chapter 5.3 --- Extension to Other Mutlidrug Scheduling Model . --- p.62 / Chapter 5.4 --- Summary --- p.65 / Chapter 6 --- DNA Sequencing by Hybridization (SBH) --- p.66 / Chapter 6.1 --- Problem Formulation: Reconstructing a DNA Sequence from Hybridization Data --- p.70 / Chapter 6.2 --- Proposed Memetic Optimization Algorithm --- p.71 / Chapter 6.2.1 --- Chromosome Encoding --- p.71 / Chapter 6.2.2 --- Fitness Function --- p.73 / Chapter 6.2.3 --- Crossover --- p.74 / Chapter 6.2.4 --- Hill Climbing Local Search for Sequencing by Hybridization --- p.76 / Chapter 6.2.5 --- Elitism and Diversity --- p.79 / Chapter 6.2.6 --- Outline of Algorithm: MA-HC-SBH --- p.81 / Chapter 6.3 --- Summary --- p.82 / Chapter 7 --- DNA Sequencing by Hybridization (SBH): Experiments and Results --- p.83 / Chapter 7.1 --- Experiment Settings --- p.83 / Chapter 7.2 --- Experiment Results --- p.85 / Chapter 7.3 --- Summary --- p.89 / Chapter 8 --- Conclusion --- p.90 / Chapter 8.1 --- Multiple Drugs Cancer Chemotherapy Schedule Optimization --- p.90 / Chapter 8.2 --- Use of the MA-IDP --- p.91 / Chapter 8.3 --- DNA Sequencing by Hybridization (SBH) --- p.92 / Chapter 8.4 --- Use of the MA-HC-SBH --- p.92 / Chapter 8.5 --- Future Work --- p.93 / Chapter 8.6 --- Item Learned --- p.93 / Chapter 8.7 --- Papers Published --- p.94 / Bibliography --- p.95