Algorithmic and combinatorial problems inspired by comparative genomics.

摘要：坐在理论计算机科学和数学的交界处，我的研究领域关注算法方法和组合工具的发展，以解决受生物学问题启发的理论问题，主要来自比较基因组学。粗略地说，比较基因组学的目的是从不同物种的基因组比较中提取信息。这些信息可能涉及基因组序列本身、基因在不同基因组中的出现顺序、小分子(如RNA)的结构等。 从产生的海量生物数据中提取有意义的信息的一般问题导致了许多关于组合对象的重要问题，如词、排列、树或图。例如，排列部分编码了基因组的结构。在这方面，开发处理这些离散结构的有效算法也是至关重要的。人们发现，在这些具体情况中的任何一种情况下，都提出了许多不同的距离概念来比较相关对象，结果是我们现在必须明确地确定这些距离中的“最佳”距离。可以肯定的是，这种距离的质量测量与构建满足预期目标的高效算法密切相关。 我的研究计划是研究人们应该如何比较和分析这些距离与它们的主要性质，并量化它们与给定的上下文的相关性。这项研究的具体结果导致了新的高效算法的构建，以帮助解决与距离优化相关的几个问题。在应用语境中距离的重要用途中，人们正在寻找一种方法，将给定问题的一组解决方案聚合为一个共识解决方案，该解决方案突出共同的期望特征，同时将分歧降至最低。我的计划的一个原创性方面在于研究如何在不同的背景下高效地(通过算法)达成这些共识解决方案。

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.