Disease-Gene Association Using a Genetic Algorithm

Understanding the relationship between genetic diseases and the genes associated with them is an important problem regarding human health. The vast amount of data created from a large number of high-throughput experiments performed in the last few years has resulted in an unprecedented growth in computational methods to tackle the disease gene association problem. Nowadays, it is clear that a genetic disease is not a consequence of a defect in a single gene. Instead, the disease phenotype is a reflection of various genetic components interacting in a complex network. In fact, genetic diseases, like any other phenotype, occur as a result of various genes working in sync with each other in a single or several biological module(s). Using a genetic algorithm, our method tries to evolve communities containing the set of potential disease genes likely to be involved in a given genetic disease. Having a set of known disease genes, we first obtain a protein-protein interaction (PPI) network containing all the known disease genes. All the other genes inside the procured PPI network are then considered as candidate disease genes as they lie in the vicinity of the known disease genes in the network. Our method attempts to find communities of potential disease genes strongly working with one another and with the set of known disease genes. As a proof of concept, we tested our approach on 16 breast cancer genes and 15 Parkinson's Disease genes. We obtained comparable or better results than CIPHER, ENDEAVOUR and GPEC, three of the most reliable and frequently used disease-gene ranking frameworks.

Modeling Metal Protein Complexes from Experimental Extended X-ray Absorption Fine Structure using Computational Intelligence

Experimental Extended X-ray Absorption Fine Structure (EXAFS) spectra carry information about the chemical structure of metal protein complexes. However, pre- dicting the structure of such complexes from EXAFS spectra is not a simple task. Currently methods such as Monte Carlo optimization or simulated annealing are used in structure refinement of EXAFS. These methods have proven somewhat successful in structure refinement but have not been successful in finding the global minima. Multiple population based algorithms, including a genetic algorithm, a restarting ge- netic algorithm, differential evolution, and particle swarm optimization, are studied for their effectiveness in structure refinement of EXAFS. The oxygen-evolving com- plex in S1 is used as a benchmark for comparing the algorithms. These algorithms were successful in finding new atomic structures that produced improved calculated EXAFS spectra over atomic structures previously found.

The use of explicit algorithms and episodic context to teach subtraction to students with learning problems in mathematics /

This research attempted to address the question of the role of explicit algorithms and episodic contexts in the acquisition of computational procedures for regrouping in subtraction. Three groups of students having difficulty learning to subtract with regrouping were taught procedures for doing so through either an explicit algorithm, an episodic content or an examples approach. It was hypothesized that the use of an explicit algorithm represented in a flow chart format would facilitate the acquisition and retention of specific procedural steps relative to the other two conditions. On the other hand, the use of paragraph stories to create episodic content was expected to facilitate the retrieval of algorithms, particularly in a mixed presentation format. The subjects were tested on similar, near, and far transfer questions over a four-day period. Near and far transfer algorithms were also introduced on Day Two. The results suggested that both explicit and episodic context facilitate performance on questions requiring subtraction with regrouping. However, the differential effects of these two approaches on near and far transfer questions were not as easy to identify. Explicit algorithms may facilitate the acquisition of specific procedural steps while at the same time inhibiting the application of such steps to transfer questions. Similarly, the value of episodic context in cuing the retrieval of an algorithm may be limited by the ability of a subject to identify and classify a new question as an exemplar of a particular episodically deflned problem type or category. The implications of these findings in relation to the procedures employed in the teaching of Mathematics to students with learning problems are discussed in detail.

Bio-inspired optimization & sampling technique for side-chain packing in MCCE

The prediction of proteins' conformation helps to understand their exhibited functions, allows for modeling and allows for the possible synthesis of the studied protein. Our research is focused on a sub-problem of protein folding known as side-chain packing. Its computational complexity has been proven to be NP-Hard. The motivation behind our study is to offer the scientific community a means to obtain faster conformation approximations for small to large proteins over currently available methods. As the size of proteins increases, current techniques become unusable due to the exponential nature of the problem. We investigated the capabilities of a hybrid genetic algorithm / simulated annealing technique to predict the low-energy conformational states of various sized proteins and to generate statistical distributions of the studied proteins' molecular ensemble for pKa predictions. Our algorithm produced errors to experimental results within .acceptable margins and offered considerable speed up depending on the protein and on the rotameric states' resolution used.

The Salmon Algorithm - A New Population Based Search Metaheuristic

This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

A Multi-Objective Genetic Algorithm with Side Effect Machines for Motif Discovery

Understanding the machinery of gene regulation to control gene expression has been one of the main focuses of bioinformaticians for years. We use a multi-objective genetic algorithm to evolve a specialized version of side effect machines for degenerate motif discovery. We compare some suggested objectives for the motifs they find, test different multi-objective scoring schemes and probabilistic models for the background sequence models and report our results on a synthetic dataset and some biological benchmarking suites. We conclude with a comparison of our algorithm with some widely used motif discovery algorithms in the literature and suggest future directions for research in this area.

Experimental and Computational Studies on Copper and Hydrobenzoin Derivatives in Catalytic Asymmetric Reactions

The use of theory to understand and facilitate catalytic enantioselective organic transformations involving copper and hydrobenzoin derivatives is reported. Section A details the use of theory to predict, facilitate, and understand a copper promoted amino oxygenation reaction reported by Chemler et al. Using Density Functional Theory (DFT), employing the hybrid B3LYP functional and a LanL2DZ/6-31G(d) basis set, the mechanistic details were studied on a N-tosyl-o-allylaniline and a [alpha]-methyl-[gamma]-alkenyl sulfonamide substrate. The results suggest the N-C bond formation proceeds via a cisaminocupration, and not through a radical-type mechanism. Additionally, the origin of diastereoselection observed with [alpha]-methyl-[gamma]-alkenyl sulfonamide arises from avoidance of unfavourable steric interactions between the methyl substituent and the N -protecting group. Section B details the computationally guided, experimental investigation of two hydrobenzoin derivatives as ligands/ catalysts, as well as the attempted synthesis of a third hydrobenzoin derivative. The bis-boronic acid derived from hydrobenzoin was successful as a Lewis acid catalyst in the Bignielli reaction and the Conia ene reaction, but provided only racemic products. The chiral diol derived from hydrobenzoin successfully increased the rate of the addition of diethyl zinc to benzaldehyde in the presence of titanium tetraisopropoxide, however poor enantioinduction was obseverved. Notably, the observed reactivity was successfully predicted by theoretical calculations.

New Contig Creation Algorithm for the de novo DNA Assembly Problem

DNA assembly is among the most fundamental and difficult problems in bioinformatics. Near optimal assembly solutions are available for bacterial and small genomes, however assembling large and complex genomes especially the human genome using Next-Generation-Sequencing (NGS) technologies is shown to be very difficult because of the highly repetitive and complex nature of the human genome, short read lengths, uneven data coverage and tools that are not specifically built for human genomes. Moreover, many algorithms are not even scalable to human genome datasets containing hundreds of millions of short reads. The DNA assembly problem is usually divided into several subproblems including DNA data error detection and correction, contig creation, scaffolding and contigs orientation; each can be seen as a distinct research area. This thesis specifically focuses on creating contigs from the short reads and combining them with outputs from other tools in order to obtain better results. Three different assemblers including SOAPdenovo [Li09], Velvet [ZB08] and Meraculous [CHS+11] are selected for comparative purposes in this thesis. Obtained results show that this thesis’ work produces comparable results to other assemblers and combining our contigs to outputs from other tools, produces the best results outperforming all other investigated assemblers.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Towards reverse engineering of Photosystem II: Synergistic Computational and Experimental Approaches

ABSTRACT Photosystem II (PSII) of oxygenic photosynthesis has the unique ability to photochemically oxidize water, extracting electrons from water to result in the evolution of oxygen gas while depositing these electrons to the rest of the photosynthetic machinery which in turn reduces CO2 to carbohydrate molecules acting as fuel for the cell. Unfortunately, native PSII is unstable and not suitable to be used in industrial applications. Consequently, there is a need to reverse-engineer the water oxidation photochemical reactions of PSII using solution-stable proteins. But what does it take to reverse-engineer PSII’s reactions? PSII has the pigment with the highest oxidation potential in nature known as P680. The high oxidation of P680 is in fact the driving force for water oxidation. P680 is made up of a chlorophyll a dimer embedded inside the relatively hydrophobic transmembrane environment of PSII. In this thesis, the electrostatic factors contributing to the high oxidation potential of P680 are described. PSII oxidizes water in a specialized metal cluster known as the Oxygen Evolving Complex (OEC). The pathways that water can take to enter the relatively hydrophobic region of PSII are described as well. A previous attempt to reverse engineer PSII’s reactions using the protein scaffold of E. coli’s Bacterioferritin (BFR) existed. The oxidation potential of the pigment used for the BFR ‘reaction centre’ was measured and the protein effects calculated in a similar fashion to how P680 potentials were calculated in PSII. The BFR-RC’s pigment oxidation potential was found to be 0.57 V, too low to oxidize water or tyrosine like PSII. We suggest that the observed tyrosine oxidation in BRF-RC could be driven by the ZnCe6 di-cation. In order to increase the efficiency of iii tyrosine oxidation, and ultimately oxidize water, the first potential of ZnCe6 would have to attain a value in excess of 0.8 V. The results were used to develop a second generation of BFR-RC using a high oxidation pigment. The hypervalent phosphorous porphyrin forms a radical pair that can be observed using Transient Electron Paramagnetic Resonance (TR-EPR). Finally, the results from this thesis are discussed in light of the development of solar fuel producing systems.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Assessing the Reproducibility of Clustering of Molecular Dynamics Conformations on Self-Organizing Maps

The goal of most clustering algorithms is to find the optimal number of clusters (i.e. fewest number of clusters). However, analysis of molecular conformations of biological macromolecules obtained from computer simulations may benefit from a larger array of clusters. The Self-Organizing Map (SOM) clustering method has the advantage of generating large numbers of clusters, but often gives ambiguous results. In this work, SOMs have been shown to be reproducible when the same conformational dataset is independently clustered multiple times (~100), with the help of the Cramérs V-index (C_v). The ability of C_v to determine which SOMs are reproduced is generalizable across different SOM source codes. The conformational ensembles produced from MD (molecular dynamics) and REMD (replica exchange molecular dynamics) simulations of the penta peptide Met-enkephalin (MET) and the 34 amino acid protein human Parathyroid Hormone (hPTH) were used to evaluate SOM reproducibility. The training length for the SOM has a huge impact on the reproducibility. Analysis of MET conformational data definitively determined that toroidal SOMs cluster data better than bordered maps due to the fact that toroidal maps do not have an edge effect. For the source code from MATLAB, it was determined that the learning rate function should be LINEAR with an initial learning rate factor of 0.05 and the SOM should be trained by a sequential algorithm. The trained SOMs can be used as a supervised classification for another dataset. The toroidal 10×10 hexagonal SOMs produced from the MATLAB program for hPTH conformational data produced three sets of reproducible clusters (27%, 15%, and 13% of 100 independent runs) which find similar partitionings to those of smaller 6×6 SOMs. The χ^2 values produced as part of the C_v calculation were used to locate clusters with identical conformational memberships on independently trained SOMs, even those with different dimensions. The χ^2 values could relate the different SOM partitionings to each other.

Optimizing Computational Frameworks to Study the Influence of the Protein Environment on the Individual Site Energies of Chromophores in Photosystem II of Photosynthesis

Photosynthesis is a process in which electromagnetic radiation is converted into chemical energy. Photosystems capture photons with chromophores and transfer their energy to reaction centers using chromophores as a medium. In the reaction center, the excitation energy is used to perform chemical reactions. Knowledge of chromophore site energies is crucial to the understanding of excitation energy transfer pathways in photosystems and the ability to compute the site energies in a fast and accurate manner is mandatory for investigating how protein dynamics ef-fect the site energies and ultimately energy pathways with time. In this work we developed two software frameworks designed to optimize the calculations of chro-mophore site energies within a protein environment. The first is for performing quantum mechanical energy optimizations on molecules and the second is for com-puting site energies of chromophores in a fast and accurate manner using the polar-izability embedding method. The two frameworks allow for the fast and accurate calculation of chromophore site energies within proteins, ultimately allowing for the effect of protein dynamics on energy pathways to be studied. We use these frame-works to compute the site energies of the eight chromophores in the reaction center of photosystem II (PSII) using a 1.9 Å resolution x-ray structure of photosystem II. We compare our results to conflicting experimental data obtained from both isolat-ed intact PSII core preparations and the minimal reaction center preparation of PSII, and find our work more supportive of the former.