Graph Structure and String Algorithms for String and Graph Reconstruction Problems

用于字符串和图重建问题的图结构和字符串算法

• 批准号: 0515378
• 负责人: Daniel Gusfield
• 金额: $ 20万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515378&HistoricalAwards=false
• 关键词: Graph; Structure; String; Algorithms; Reconstruction

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.

这个建议涉及图论和字符串算法交叉的算法和结构问题。 这些问题集中在推导一组字符串在某些操作下，其中重组是最重要的，图形被用来显示解决方案，并获得解决方案。 这是非平凡的作用，图在获得解决方案，形成了这个建议的基础。 我们最近利用某些图的结构方面，并利用图算法来解决一些字符串问题。 该项目将更深入地研究相关的图结构和图算法，并将其连接到解决一类特定的算法字符串问题。 关注的特定字符串问题起源于一个生物尺度的群体遗传学，以及不同生物尺度的遗传学。更广泛的影响我们将开发的算法和软件可能使生物学家更好地了解重组，基因转换和横向基因转移的历史和作用。 仅举两个例子，这些工具将通过关联映射促进基因发现的任务，并了解横向基因转移如何帮助细菌快速产生抗生素耐药性。