Algorithmic and combinatorial studies inspired by problems of comparative genomics

我的研究兴趣是开发算法方法和组合工具，以解决由比较基因组学领域中出现的生物学问题引发的理论问题。比较基因组学的基本目标之一是从不同物种的基因组比较中提取信息。这些信息涉及基因组序列本身、基因在不同基因组中的出现顺序、小分子(如RNA)的结构等。从由此产生的大量生物信息中提取有意义的信息的一般问题引发了许多关于词、排列、树或图的精细组合学的重要理论问题。我的研究计划的第一部分涉及到对代表非编码RNA(NcRNA)结构的特殊树和图的研究和比较。这项研究对生物学特别重要，因为ncRNA的重要细胞功能依赖于它们的结构和组合特性。此外，ncRNA结构的复杂数据库的快速扩展(从2002年的仅有3个已知家族到今天的1,400多个)需要开发更快的算法来比较和分析这种结构。第二部分涉及对代表不同基因组中基因出现顺序的排列或符号排列的研究。这里的问题在于找到一组排列在距离d下的中位数，并受到比较基因组学中的基因顺序问题的启发，在比较基因组学中，不同物种基因组中基因出现顺序的差异被用来评估它们之间的进化距离。最后，在生物信息学领域开发更高效的比较算法将产生预期的理论结果，这必将有助于解决其他计算机科学领域的类似问题。我们已经展示了我们的结果如何应用于软件工程的上下文中，在软件工程中，系统的维护需要在程序代码中搜索反复出现的主题。

My research interests are in developing algorithmic approaches and combinatorial tools to solve theoretical problems inspired by biological problems arising in the field of comparative genomics. One of the basic aim of comparative genomics is to extract information from the comparison of genomes of different species. This information concerns the genomic sequence 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 mass of biological information gives rise to many important theoretical problems on the fine combinatorics of words, permutations, trees or graphs. A first portion of my research program concerns the study and comparison of special trees and graphs representing non-coding RNA (ncRNA) structures. This study is of particular importance for biology because important cellular functions of ncRNA depend on their structural and combinatorial properties. Moreover, the fast expansion of complex databases of ncRNA structures (from barely 3 known families in 2002, to over 1,400 today) warrants the development of faster algorithms for the comparison and the analysis of such structures. A second portion concerns the study of permutations or signed permutations representing the order of appearance of genes in different genomes. Here, the problem consists in finding the median of a set of permutations under a distance d and is inspired by the gene order problem of comparative genomics, where the difference in order of appearance of genes in the genome of different species is used to evaluate the evolutionary distances between them. Finally, the expected theoretical results that will arise from the development of more efficient comparison algorithms in the field of bioinformatics is bound to help to solve similar problems in other field of computer science. We have already shown how our results may be applied in the context of software engineering where the maintenance of system requires the search of recurrent motifs in a program code.