Algorithms for the Analysis of Approximate Gene Cluster (3AGC)

基因在基因组中的顺序可以用来确定未知基因的功能，以及生物体的系统发育历史。鉴于基因组测序的速度不断加快，这类研究存在着海量的数据。然而，在算法方面，方法往往基于过于简化的基因组模型，使用启发式算法来解决优化问题，或者运行时间较长。基因簇是以单个连续块出现在几个基因组中的一组基因。遗憾的是，对于生物学应用来说，对基因簇的准确出现的要求太严格了。在这个项目中，我们想要开发计算近似基因簇的模型和算法，将形式上的严密性与对生物数据的适用性结合起来。与此同时，我们的算法必须快速，以允许应用于越来越多的基因组数据。我们将把组合优化和算法图论的方法与统计上合理的评估相结合。我们将实施、培训和评估我们的方法，以实现基因顺序数据的自动化处理。最后，我们希望将我们的方法应用于生物数据，以获得对基因功能的新见解。

The order of genes in genomes can be used to determine the function of unknown genes, as well as the phylogenetic history of the organisms. In view of the ever-increasing speed of genome sequencing, there exists a huge amount of data for such studies. On the algorithmic side, though, methods are often based on overly simplified genome models, use heuristics to solve optimization problems, or suffer from long running times.Gene clusters are sets of genes that occur as single contiguous blocks in several genomes. Unfortunately, the requirement of exact occurrences of gene clusters turns out to be too strict for the biological application. In this project, we want to develop models and algorithms for the computation of approximate gene clusters, that combine a formal strictness with applicability to biological data. At the same time, our algorithms must be swift to allow application to the increasing amount of genome data. We will combine methods from combinatorial optimization and algorithmic graph theory with a statistically sound evaluation. We will implement, train, and evaluate our methods to allow an automated processing of gene order data. Finally, we want to apply our method to biological data, to derive new insights about gene function.