Graph Structure and String Algorithms for String and Graph Reconstruction Problems

点击翻译按钮获取中文摘要

This proposal concerns algorithmic and structural problems at the intersection of graph theory and string algorithms. The problems center on the derivation of a set of strings under certain operations, of which recombination is the most important, and graphs are used both to display the solution, and to obtain the solution. It is the non-trivial role of graphs in obtaining the solution that forms the basis for this proposal. We have recently exploited structural aspects of certain graphs, and exploited graph algorithms to solve a number of string problems. The proposed project will more deeply study the relevant graph structure and graph algorithms and connect it to solve a specific class of algorithmic string problems. The specific string problems of concern originate in population genetics at one biological scale, and in phylogenetics at a different biological scale.Broader ImpactThe algorithms and software that we will develop may allow biologists to better understand the history and role of recombination, gene-conversion and lateral gene transfer. As just two examples, the tools will facilitate the tasks of gene finding by association mapping, and in understanding how lateral gene transfer helps bacteria to rapidly develop antibiotic resistance.