Investigations in Combinatorial Optimization and its Applications to DNA Sequencing Problems

本研究主要针对最小权值共同变异序列（MWCMS）问题进行理论与计算研究。这项研究的动机是希望帮助量化的概念，“最佳”代表序列的进化距离问题。进化距离问题涉及到找到与一个物种相关的最可能的祖先的DNA序列。 给定一组来自不同但相似的生物体的DNA序列。 该项目由四个部分组成：（1）开发逼真的基于图的模型来描述MWCMS问题。该模型包括利用DNA序列建立多层超图和基于完整路径集合的冲突图，（2）研究模型的复杂性，（3）研究求解大规模节点填充实例的计算求解策略，（4）研究基于冲突图的求解算法。以及（4）将所开发的方法应用于发现与“肿瘤抑制基因”失活相关的不同基因序列之间的模式和相似性的肿瘤学问题，这是一种导致异常细胞增殖的现象，这是癌症的标志。这项研究的成功将导致与最小权重共同突变序列问题相关的重要理论结果;它将扩展和/或推广已知的复杂性结果，用于已研究的排序问题的类别;它将有助于理解进化距离问题和基因组分析;它将导致解决大规模节点填充问题的计算技术的进步，这些问题通常出现在工业应用中，尤其是在我们的DNA测序研究中。肿瘤学应用将帮助癌症生物学家和肿瘤学家更好地了解基因序列中可能导致“肿瘤抑制基因”失活的隐藏模式。这些基因的失活导致异常细胞增殖，这是癌症的标志。因此，该研究将有助于在基因组水平上更好地了解重要的癌症形成机制。 教育推广包括为工程和医学领域的本科生和研究生编写与该项目有关的教材。它还包括培养两名博士。学生在这个涉及优化，算法设计和癌症治疗的多学科研究。 除了会议和公开小组讨论，该研究项目的一部分也将在信息和生物技术的讲座中传播“癌症生物学和生物技术”，最近由格鲁吉亚理工学院的一组跨学科教师研究人员开发，重点是多方面的方法来推进癌症技术。

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.