论文部分内容阅读
高通量生物实验技术，例如基因芯片、质谱分析、二代测序等，已经成为了生物医学研究中不可或缺的工具。这些高通量实验的后续分析通常会产生一个基因集作为输出结果，这个集合中的基因是按照某种准则和方法选取的，因而具有某些共同的特征，比如差异表达。如何去解释这些基因集背后的生物学意义，换句话说，如何去学习这些被选出来的基因之间的功能关系及其所包含的生物学机理机制，仍然是一个有挑战性的问题。 基因本体论(Gene Ontology，GO)统一了所有物种的基因及基因产物功能注释的表示方式。这个计划的主要目的是去维护和发展一套关于基因和基因产物功能注释的词汇，并用这套词汇去解释基因和基因产物。自从基因本体论注释计划被全面启动，大量旨在挖掘分析基因本体论数据的工具被开发出来，尤其是各种各样的以基因本体论为基础的功能富集分析工具。 基因集功能富集分析的方法多种多样，从这些方法要求的输入信息来看可以大致分为两类:第一类方法只需利用一个选出的基因集合，第二类方法不对基因进行预筛选，而是使用全部基因作为输入。例如要作一组差异表达基因的功能富集分析，第一类方法的输入仅为一个我们认为存在差异表达的基因集合，而第二类方法的输入是所有基因的表达数据。某种程度上可以认为第二类方法是差异分析加功能富集分析的整合。 本文关注的是基因集产生之后的功能富集分析过程，也就是以上说的第一类方法。我们从最原始的功能富集分析出发，从优化的角度重新构建了多个基因功能富集分析的方法。 本文提出了一个新的基于网络信息的功能富集分析方法。该方法可以使用某种指定的基因网络来辅助分析，使得分析结果具有更强的鲁棒性和解释力。我们通过大量的模拟数据和真实数据来对新方法进行检验和评价，并且将结果和已有的算法和模型进行比较。实验结果说明这个基于网络的功能富集分析方法是非常有效的，能够挖掘出一般的基因功能分析不能发现的信息。 本文还提出了一个基于组合优化的基因富集分析方法。该方法从最经典的基于超几何分布的功能富集分析模型出发，从组合优化的角度重新定义了功能富集分析模型，并设计了有效的近似算法来解决这个困难的组合优化问题。我们通过大量的模拟数据和真实数据来对新方法进行检验和评价，并且将结果和已有的算法和模型进行比较。新方法能够更快更好地发现显著富集的功能条目组合，帮助生物学家从系统的角度深入理解基因集中所富含的信息。新方法还能够有效地去除基于单一条目分析方法的结果中的大量冗余信息，为后续的生物学分析和实验提供了极大的便利。 本文对基因功能富集分析问题进行了深入和系统的研究，针对不同类型的问题，建立了多个优化模型并设计了求解算法，在模拟数据和实际生物数据上的验证表明我们的新模型和算法达到了预期目的，改进了现有的功能富集分析方法，有很强的实际应用价值。另一方面，本文在组合功能富集分析模型中提炼出来的富集集覆盖问题(Enrichment Set Cover Problem)，建立了集覆盖问题的一个新的变种，扩展了集覆盖问题的研究和应用领域，对于运筹学理论和算法的研究也具有重要意义。