论文部分内容阅读
人类基因组计划(HGP)的顺利进行使得人类逐渐步入了以基因组的诠释评估与功能解析为主的后基因组时代。为了研究基因变异和疾病间的关联关系以及基因遗传变异的过程，我们需要知道SNP在每个人的两条染色体上是如何组合、分布的。位于同一条染色体上某一区域的一组相关联的SNP信息被称作单体型(haplotype)。得到单体型数据是整个SNP研究的第一步，是SNP相关研究和应用的关键基础。 目前直接检测单体型的生物实验技术还不成熟，不仅费用高昂而且周期很长。一个可行的替代方法就是利用计算机软件分析一些比较容易获得的实验数据，例如基因型数据、SNP片断数据等等，来推断单体型。根据所使用的生物实验数据，现有的单体型检测模型可以分为两大类:单体型组装(HaplotypeAssembly)和单体型推断(Haplotype Inference)。单体型组装则是利用DNA测序得到的个体SNP片断来拼接出较长的单体型，而单体型推断是从一个群体的基因型数据出发，利用各种数学和遗传学假设来推断与基因型对应的单体型。 本文首先介绍了单体型检测问题的数学模型与算法的研究历史和现状，然后分别对两个问题进行深入的研究。对于单体型推断问题，我们研究了最新的马尔可夫链模型(Markov Chain)。马尔可夫链模型最早是由芬兰学者Eronen提出的，由于对较长的单体型推断问题效果很好而得到了学术界的关注。现有的马尔可夫链模型采用的是启发式近似算法，对于解的质量没有保障。我们提出了一个统一现有马尔可夫链模型的框架，并基于这个框架设计了多项式时间的精确算法。对于单体型组装问题，我们研究了最接近实际应用的最小错误纠正模型(Minimum Error Correction)，包括计算复杂性、近似算法和精确算法。此外，针对MEC模型的不足，我们还提出和研究了几个扩展模型及其算法。