Structure-aware models and algorithms for reconstructing the evolution and ancestral states of genes and genomes

这是一个计算基因组学研究项目，旨在解决算法和计算问题，以提高我们对基因组进化的理解。目前，大多数基因组进化重建方法都局限于利用基因组的序列保守部分，对组成部分的结构关注较少。然而，目前在生命科学方面的发现正在揭示基因结构的复杂性及其对基因功能和进化的重要性。特别是，非编码rna （ncRNAs）的二级结构和真核编码基因的结构为基因进化和祖先状态的重建提供了有价值的信息。******该项目的长期目标是开发一种综合方法，利用ncRNA折叠结构和基因结构信息，利用非编码和编码基因重建基因和基因组的进化和祖先状态。对于本提案，两个五年目标的重点是开发模型和算法来重建ncRNA二级结构和编码基因结构的进化和祖先状态。******实现这些目标的方法包括首先设计改进的基因进化模型，该模型考虑了编码基因结构和ncRNA二级结构的全部信息。其次，我们将在改进的进化模型下考虑各种生物启发优化问题，研究其理论复杂性并设计适当的算法解决方案。我们将利用物种树、基因同源关系和建筑/结构信息在综合方法中重建进化历史和推断祖先状态。我们会开发易于使用的软件，提供给社会各界使用和维护。******这个计划的影响将是，首先，有助于更好地理解基因和基因组结构的进化，并提供有效的程序和软件来计算分析这些结构。其次，该计划将有助于培养高素质的人才，在一个日益增长的，苛刻的，高度多学科领域。第三，它将产生理论和算法，这些理论和算法可能会揭示出与多尺度结构、树和图上更普遍的问题之间有趣的联系。

This is a computational genomics research program aimed at solving algorithmic and computational problems in order to improve our understanding of genome evolution. Currently, most genome evolution reconstruction methods are limited to the use of sequence-conserved portions of genomes, paying less attention to the structure of components. However, current discoveries in the life sciences are shedding new light on the complexity of gene structure and its importance for gene function and evolution. In particular, the secondary structure of non-coding RNAs (ncRNAs) and the architecture of eukaryotic coding genes constitute valuable information for the reconstruction of gene evolution and ancestral states. ******The long-term objective of this program is to develop an integrative approach for reconstructing gene and genome evolution and ancestral states using non-coding and coding genes, while making use of ncRNA folding structure and gene architecture information. For this proposal, the two five-year objectives focus on developing models and algorithms for reconstructing the evolution and ancestral states of ncRNA secondary structures and coding gene architectures.******The methodology to reach these objectives consists in first designing improved gene evolution models that take into account full information about coding gene architecture and ncRNA secondary structure. Second, we will consider various bio-inspired optimization problems under the improved evolutionary models, study their theoretical complexity and design appropriate algorithmic solutions. We will use species trees, gene homology relations and architecture/structure information in an integrative approach to reconstruct evolutionary histories and infer ancestral states. We will develop user-friendly software that will be made available and maintained for the community.******The impacts of this program will be, first, the contribution to a better understanding of gene and genome structure evolution and the availability of efficient programs and software for computational analyses of these structures. Second, the program will contribute to the training of highly qualified personnel in a growing, demanding, highly multidisciplinary field. Third, it will yield theories and algorithms that are likely to reveal interesting links with more general problems on multiscale structures, trees and graphs.