Investigations in Combinatorial Optimization and its Applications to DNA Sequencing Problems

本文对最小权值共突变序列（MWCMS）问题进行了理论和计算研究。这项研究的动机是为了帮助量化进化距离问题中“最佳”代表序列的概念。进化距离问题涉及到找到最可能的祖先的DNA序列，这些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.