Investigations in Combinatorial Optimization and its Applications to DNA Sequencing Problems

本文主要对最小重量公共突变序列问题进行了理论和计算研究。这项研究的动机是希望帮助量化进化距离问题中“最佳”代表序列的概念。进化距离问题涉及从不同但相似的生物体中寻找与给定的一组DNA序列相关的最可能祖先的DNA序列。该项目由四个部分组成：(1)开发基于图形的逼真模型来描述MWCMS问题。这些模型包括使用DNA序列建立多层超图，并基于完整路径的集合构建冲突图；(2)研究底层模型的复杂性；(3)研究用于解决由此产生的大规模节点填充实例的计算解决策略；以及(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.