计算机和网络技术的飞速发展，为分子生物学研究提供了新的强大手段。单体型信息因其在医学特别是遗传疾病研究方面具有重要意义，引起生物与医学工作者的极大关注。但绝大多数所研究的生物个体，包括人类自身，都是双倍体结构；目前由于时间和经济成本上的约束，在实验室里只能得到双倍体结构的复合基因型序列。因此，当需要知道物种或者组织的单体型序列信息时，我们必须借助于计算手段，将每一条基因型序列分解为两条单体型序列，这就是单体分型问题。本文研究了不同数据集及不同模型上单体分型问题的计算复杂性，设计和实现了一系列高效的单体分型和单体型频率估计算法。其主要内容和贡献包括： (1)群体数据集单体分型群体数据集不包含任何家系信息，是最常见的一种基因型数据集。关于群体数据集单体分型问题，目前常见的计算手段有Clark算法、PPH算法以及EM和GS等概率统计算法。本文对一种新近提出的基于最大节约原则的单体分型(HMP)模型进行了研究，证明其是NP-hard的和APX-hard的(即，除非NP=P，否则存在一个常数e＞0，该问题没有比1+e好的多项式时间逼近算法)。因此，我们为其设计了一个多项式时间的贪心算法以及一个将贪心策略和分支限界策略集合在统一框架下的复合算法。实验结果表明：贪心算法在保持了较准确分型结果的基础上，运行速度相当快；而复合算法虽是完全算法，但其运行效率和实例规模比原有的分枝限界算法都得到了极大提高。群体数据集中特定基因型序列分型(SGH)判定问题与上述Clark算法相关，它可以帮助我们更好理解单体分型问题。本文证明了SGH问题为NP-complete的。 (2)家系数据集单体分型由于家系信息的对单体构型的限制，基于家系数据集进行的单体分型和单体型频率估计的结果会更加可靠。目前对其研究集中于寻找使得家系中发生最少重组事件的单体构型。本文提出了一个k-最少重组单体分型(k-MRH)模型，它在现有的最少重组单体分型(MRH)模型中引入额外限制，使得重组事件在家系中更加合理地平衡分布。同时设计了k-MRH模型的一个综合了寻根策略的优化动态规划算法，尽管该模型也是NP-hard的，但我们的限制条件使其解空间大大缩小，从而大大提高了算法的搜索效率，这在模拟和实际数据的实验中都得到了验证。 零重组单体分型(ZRH)问题是MRH问题一个特例，其目标是为给定家系求解不包含任何重组事件的单体构型，它在单体分型以及单体型频率估计方面具有重要意义。本文给出了ZRH问题的一个最优的线性时间算法：HCL-连锁分析单体分型算法。 (3)家系数据集单体型频率估计单体型频率估计和单体分型问题密切相关，本文提出了一个两段式的家系数据集单体型频率估计方法：i)、单体分型阶段：用HCL-连锁分析单体分型算法找出所有零重组单体构型；ii)，频率估计阶段：发展了原有针对群体数据集的EM算法以在前一阶段得到的单体构型上进行频率估计，并且使用分割-合并技术，将原指数时间的EM算法改造为近似线性时间算法。 以前的直接估计法不考虑家系信息，必须对所有可能的单体型序列进行估计。而我们的两段式方法多了一个分型阶段，该阶段排除了大量不合理和不重要的单体构型。因此，整个频率估计时间大为减少，结果也更加可靠这些都从实验中得到了验证。 按照研究内容分类，本文的创新之处在于：1、群体数据集单体分型证明了HMP模型为NP-hard和APX-hard的；SGH问题为NP-complete的；并为HMP模型成功设计了一个贪心算法和一个复合完全算法，它们能够解决较大规模的问题实例。 2、家系数据集单体分型在MRH模型基础上，提出了一个更加合理的k-MRH模型；并为其设计了一个优化动态规划算法，该算法能够解决大部分实际的k-MRH问题；给出了MRH问题的特例——ZRH问题一个最优的线性时问算法。 3、家系数据集单体型频率估计首次明确指出零重组单体构型可以作为家系数据集单体型频率估计的基础；并由此为后者设计了一个两段式方法，比起以前的直接估计法，该方法所需时间大为减少，结果也更加可靠。