Weixiong Zhang - US grants

Abstract
Zhang 0113618
Korf 0113313

Best-First Search Algorithms for Sequence Alignment Problems in Computational
Biology

Molecular biologists are currently faced with very challenging computational problems. For example, a draft of the human genome has been completed, a sequence of about three billion base pairs. A draft of the mouse genome soon will be completed. We know that mice and men share over 90% of their genetic material. What we don't know is exactly which parts of the human and mouse genomes are common to both species. This information can be used to identify human genes, and to translate results from mouse studies to studies of human health and disease. The problem of identifying the common elements between these two DNA sequences is an example of sequence alignment, which is a computational problem. Other examples of sequence alignment problems include gene identification, and RNA and protean structure prediction. Current computer algorithms are either too slow, or require too much memory, to directly solve a problem as large as the human-mouse genomic sequence alignment. We propose to develop new algorithms for various sequence-alignment problems, based on heuristic search algorithms in artificial intelligence. Our goal is to provide much more efficient sequence-alignment algorithms for use by molecular biologists.

This project studies general purpose heuristic problem solving through development of (1) efficient strategies and algorithms for solving combinatorial optimization problems, and (2) effective methods for exploiting intrinsic problem features of phase transitions and "backbones" -- that is, variables that need to be fixed among all optimal solutions -- to solve these problems. The general approach of this project is to mechanize problem solving using mathematical means. Each of the two research thrusts of the project involves several subtopics. The first thrust is to develop a general approach to heuristic problem solving that involves a new set of methods for automatically developing heuristic strategies and search algorithms. It employs a representation scheme using a constraint programming paradigm, a set of constraint manipulation methods for deriving heuristic functions, and a learning scheme to automatically determine the 'right' combination of heuristic functions and search methods for a given problem. The second thrust focuses on utilizing intrinsic problem features, particularly phase transitions and backbones. The project plans to consider a variety of problems, including combinatorial optimization problems (e.g., the Traveling Salesman Problem), constraint optimization problems (e.g., scheduling and resource allocation), and complex optimization problems in computational biology (e.g., sequence alignment and haplotype inferencing). The results of this research could have a very broad impact in computer science and beyond (e.g., operations research, computational molecular biology) due to the great variety of problems that can be approached through heuristic search and combinatorial optimization.

Washington University has been awarded a three year grant to study the expression of genes in plants under abiotic stress. The resulting understanding of stress response mechanisms will lead to understanding and potential interventions in crop yield loss attributable to drought, cold and salinity and develop methodologies for research of other stressors. These discoveries will be enabled through a set of machine learning and data mining tools that will allow for functional analysis of a large collection of previously generated gene expression data. The computational tools will be web accessible or may be installed by other researchers as standalone applications so that other research teams can apply the methods to new expression data as it becomes available. This project will identify cis-regulatory elements and motif modules. It will create models of transcription regulation as well as co-expression networks. The project will cooperate with the Washington University?s Science Outreach Program to provide professional development opportunities for K-12 teachers.

DESCRIPTION (provided by applicant): Identification of even a single gene that contributes to a complex trait provides insight into its molecular basis. However, multiple genes need to be identified if different genes affect a trait through different biological processes or pathways. In the context of pharmacological treatments, each gene is relevant to attaining effective therapy and avoiding adverse drug reactions. While both linkage mapping and association studies have proved to be effective tools for analysis of complex traits, they rarely identify more than one or a small number of genes per study and each gene requires considerable effort to fine-map. The goal of the proposed research is to use S. cerevisiae as a model system to understand the diversity of molecular mechanisms by which different genes affect colony color, a drug-dependent quantitative trait. The first aim of the proposed research will determine whether multiple genes can be identified by a quantitative non-complementation screen using the yeast deletion collection. Reciprocal hemizygosity analysis will be used to estimate the rate of false positives due to haplo-insufficiency and second site mutations within the deletion collection. The second aim of the proposed research will characterize the relationship between colony color alleles by identifying downstream changes in gene expression. A quantitative model of colony color will be generated based on changes in gene expression associated with colony color and the model's ability to predict the effects of genetic background will be tested using recombinant strains segregating both known and unknown colony color alleles. Together, these aims will provide insight into the diversity of molecular mechanisms by which different genes influence a trait and how their effects are modified by genetic background. PUBLIC HEALTH RELEVANCE: Complex traits are the product of multiple genes, their interactions with each other, and their interactions with the environment. Although a number of methods are available to identify one or a few genes involved in a complex trait, it has been difficult to systematically identify every gene underlying a trait and the mechanisms by which they influence a trait. The proposed research will develop and evaluate a method of identifying multiple genes that contribute to complex traits and a model to predict their dependence on genetic background using gene expression data.

DESCRIPTION (provided by applicant): This application addresses broad Challenge Area (06) Enabling Technologies and specific Challenge Topic: 06-AR-103, Systems Biology for Skin and Rheumatic Diseases. Psoriasis (PS) is a complex inflammatory skin disease where genetic risk factors and environmental trigger contribute to the "rewiring" of the circuitry of the transcriptome of the skin. Until now an understanding of its systems biology of psoriasis were limited by genomic tools that were neither cost effective, nor comprehensive. PS affects as many as 7.5 million Americans (2-3% of the population) and between 10 and 30 percent of PS patients develop psoriatic arthritis (PsA). Both PS and PsA are serious conditions for which there are no cures, and warranting sophisticated medical care and therapies. Total direct and indirect health care costs of PS patients are ~ $11.25 billion annually. PS can cause as much disability as other major diseases, including diabetes, heart disease, hypertension and depression accompanied by thoughts of suicide. It goes hand-in-hand with myriad co-morbid conditions such as Crohn's disease, diabetes, metabolic syndrome, obesity, hypertension, heart attack, cardiovascular disease and liver disease. Despite progress in understanding altered cellular pathways and genetic risk factors of PS, it is still poorly understood. Current treatments present a challenge for patients and their health care providers because no one treatment works for everyone, some treatments lose effectiveness over time, many treatments used are in combination with other treatments, and all treatments may cause a unique set of side effects. With the development of high throughput Next-Generation DNA sequencing we are proposing to identify altered mRNAs, and small noncoding RNAs (including microRNAs) and model the altered networks of this disease. These data will also be a rich resource of deep sequence profiling data that will facilitate research by the psoriasis community. Moreover, altered networks of this disease may pave the way for targeted therapeutic intervention. This is a collaborative proposal from investigators who have pioneered the analysis of the psoriasis transcriptome, the development of tools for the analysis of expression and microRNA sequence datasets, and network building. The high throughput, and technological prowess of the genome sequencing center at Washington University school of medicine and the development of methods for massively parallel genome sequencing are technologies enabling the work described in this proposal. Our multidisciplinary collaborative group has proven expertise both in sample and library preparation methods, Next-Generation sequencing methods and computational analysis to complete the aims of this proposal in a two year time-period. Psoriasis is an inflammatory disease of the skin for which there is no cure. It affects many individuals worldwide, and 2-3% of Americans. The expected outcome of this study is the identification of novel networks and cellular factors in psoriasis (PS) that can be targeted for the development of novel treatments. )

DESCRIPTION (provided by applicant): Systems-biology methods based on co-expression (co-exp) networks are powerful tools for understanding complex diseases. In a co-exp network, nodes represent genes, edges represent significant correlations between pairs of genes, and a module of connected nodes captures possible functional associations among the genes. Co-exp network methods have been successfully applied to understanding genetic architecture of human population and mechanisms of complex diseases, such as Alzheimer's disease and diabetes. Despite their success in biological and medical applications, the current co-exp network methods are unable to deal with genetic heterogeneity in the cohorts of samples of interest. Genetic heterogeneity is inherent in the cohorts of cases and controls in most complex disease studies. Therefore, failure to accommodate genetic heterogeneity will result in incorrect co-exp network structures and consequently lead to erroneous causal relationships between genetic variations and disease phenotypes. However, development of co-exp network methods that are adaptive in the presence of genetic heterogeneity is a challenge since no proper correlation measure that is resilient to genetic heterogeneity currently exists, which seriously limits the power and applicability of co-exp network analysis. To address this challenge, we introduce a new correlation measure of gene expression that is resilient to genetic heterogeneity and propose a novel individual-centric co-exp network approach to honor genetic heterogeneity. Our initial application of these methods to a set of gene expression data of Alzheimer's disease produced an impressive co-exp network module with coherent functions that are associated with the disease. This preliminary result provided the first set of convincing evidence on the validity of the new methods. In the proposed research, we will fully develop our novel co-expression network approach (Aim 1). In order to make the approach robust in the presence of genetic heterogeneity and noise in gene expression data, we will introduce a series of rigorous and unbiased tests for validating statistically and biological significant network modules (Aim 2). Furthermore, we will extend our approach to integrate the results of co-exp network modules with information of genetic variations to support genetics of gene expression studies (Aim 3). We will apply the new methods to Alzheimer's disease, psoriasis and prostate cancer, to examine the validity of our approach and more importantly, to gain deep insights into the genetic bases of these complex diseases that burden a substantial proportion of the human population (Aim 4). Finally, we will develop a software package of our methods, which will be freely available, and a web-based online service to the research community to ease the computational burden in complex disease studies (Aim 5). The proposed research represents a fundamental paradigm shift from conventional analyses of gene expression data and has the potential for significant advancements for the research of complex diseases as well as other population variations.