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.