Algorithmic and combinatorial problems inspired by comparative genomics.

受比较基因组学启发的算法和组合问题。

• 批准号: RGPIN-2016-04576
• 负责人: Hamel, Sylvie
• 金额: $ 1.6万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=709381
• 关键词: Algorithmic; combinatorial; problems; inspired; comparative

Abstract: Sitting at the interface of theoretical computer science and mathematics, my area of research concerns the development of algorithmic approaches and combinatorial tools for theoretical problems inspired by biological problems, coming mostly from comparative genomics. Roughly speaking, comparative genomics aims at extracting information from the comparison of genomes of different species. This information may concern genomic sequences themselves, the order of appearance of genes in different genomes, the structure of small molecules (like RNA), etc. The general problem of extracting meaningful information from the resulting very large mass of biological data gives rise to many important problems on combinatorial objects such as words, permutations, trees or graphs. For instance, permutations partially encode the structure of genomes. The development of efficient algorithms for the manipulation of these discrete structures is also crucial in this context. One finds that, in any one of these specific contexts, many different notions of distances have been suggested to compare the relevant objects, with the consequence that we now have to clearly characterize the ``best'' distances among these. For sure, this quality measurement of distances is closely tied to the construction of efficient algorithms fulfilling the desired goal. My research program consists in studying how one should compare and analyze such distances with respect to their principal properties, and to quantify their relevance to a given context. Concrete results of this study lead to the construction of new efficient algorithms to help solve several problems related to distances optimization. Among important uses of distances in applied contexts one looks for a way to aggregate a set of solutions of a given problem into a consensus solution which highlights common desired features, while minimizing disagreements. One original aspect of my program rests on the study of how to efficiently (algorithmically) reach these consensus solutions in various context.

摘要：作为理论计算机科学和数学的交汇点，我的研究领域涉及受生物学问题启发的理论问题的算法方法和组合工具的发展，主要来自比较基因组学。粗略地说，比较基因组学旨在从不同物种的基因组比较中提取信息。这些信息可能涉及基因组序列本身，不同基因组中基因的出现顺序，小分子（如RNA）的结构等。