计算机和网络技术的飞速发展，为分子生物学研究提供了新的强大手段。单体型信息因其在医学特别是遗传疾病研究方面具有重要意义，引起生物与医学工作者的极大关注。但绝大多数所研究的生物个体，包括人类自身，都是双倍体结构；目前由于时间和经济成本上的约束，在实验室里只能得到双倍体结构的复合基因型序列。因此，当需要知道物种或者组织的单体型序列信息时，我们必须借助于计算手段，将每一条基因型序列分解为两条单体型序列，这就是单体分型问题。本文研究了不同数据集及不同模型上单体分型问题的计算复杂性，设计和实现了一系列高效的单体分型和单体型频率估计算法。其主要内容和贡献包括： (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的，但我们的限制条件使其解空间大大缩小，从而大大提高了算法的搜索效率，这在模拟和实际数据的实验中都得到了验证。