Investigations in Combinatorial Optimization and its Applications to DNA Sequencing Problems

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This research focuses on theoretical and computational investigations of the minimum weight common mutated sequence (MWCMS) problem. The study is motivated by the desire to help quantify the concept of "best" representative sequence in the evolutionary distance problem. The evolutionary distance problem involves finding the DNA sequence of the most likely ancestor associated with a given a set of DNA sequences from distinct but similar organisms. The project consists of four parts: (1) Develop realistic graph-based models to describe the MWCMS problem. The models involve setting up a multi-layer supergraph using the DNA sequences, and construction of conflict graphs based on a collection of complete paths; (2) Study the complexity of the underlying models; (3) Investigate computational solution strategies for solving the resulting large-scale node-packing instances; and, (4) Apply the methods developed to the oncological problem of finding patterns and similarities among different gene sequences linked with inactivation of "tumor suppressor'' genes, a phenomenon which leads to abnormal cell proliferation, which is a hallmark of cancer. Success of this research will lead to important theoretical results related to the minimum weight common mutated sequence problem; it will expand and/or generalize known complexity results for classes of well-studied sequencing problems; it will help to understand the evolutionary distance problem and genomic analysis; and it will lead to advances in computational techniques for solving large-scale node packing problems, problems that arise commonly in industrial applications, and specifically in our study to DNA sequencing problems. The oncological application will help cancer biologists and oncologists to better understand hidden patterns in gene sequences which may be responsible for inactivation of "tumor suppressor'' genes. Inactivation of such genes leads to abnormal cell proliferation, a hallmark of cancer. Hence, the study will help to gain a better understanding of an important cancer formation mechanism at the genomic level. Educational outreach involves developing teaching materials related to the project for undergraduate and graduate students in engineering and in the medical domain. It also involves training two Ph.D. students in this multidisciplinary research involving optimization, algorithmic design and cancer treatment. In addition to conferences and public panel discussions, part of the research project will also be disseminated in the lectures on information and biotechnology in the course "Cancer Biology and Biotechnology", developed recently by a group of interdisciplinary faculty researchers at Georgia Tech with a focus on multi-faceted approaches for advancing cancer technology.