单核苷酸多态性（SingleNucleotidePolymorphism，SNP）是指在基因组水平上由单个核苷酸变异所引起的DNA序列的多态性。在各类单体型中，少部分SNP位点包含绝大部分的遗传变异信息，这些位点称为标志SNP位点（TagSNP或htSNP）。通过生物实验从基因型序列中获取确定的单体型序列，即单体分型（Haplotyping）可以得到比较精确、可靠的结果。然而，代价高昂，难以满足当前海量生物数据分析。因此，借助数学和计算机结合的计算分子生物学手段寻找TagSNP位点，是解决单体分型问题的一个有效途径。　　本文对TagSNP位点选择问题进行了详细的阐述，并在充分研究和分析当前SNP位点选择算法的基础上，创新性地提出了基于图的TagSNP位点选择算法MDStagger，有效的提高了预测精确度，缩短了算法的运行时间。　　具体地，本文的主要研究内容和创新点如下：　　第一，描述了TagSNP位点的选择问题，包括解决该问题的数学模型和算法思想。同时，本文还分析了这些算法的优缺点及各自适用的范围。　　第二，提出了基于图的TagSNP位点选择算法MDStagger。文中阐述了图模型的构建法则以及将SNP位点的信息转化为最大密度子图的思想。重点描述了通过最大密度子图来寻找TagSNP位点的思想。实验表明，该算法能够避免因为随机算法带来的局部最优问题和枚举法产生的高时间复杂度等问题，与当前主要的TagSNP位点选择算法相比较，具有较优性能。　　第三，提出了一种改进的精确度预测方法，该方法基于多TagSNP位点联合预测非TagSNP位点。实验表明，多TagSNP位点联合预测比单一TagSNP位点预测，能够得到更高的精确度。该预测方法不仅提高了精确度，同时也为SNP位点评价准则的改进以及缺失位点的预测指明了一个新的方向。　　第四，实现了TagSNP位点选择算法及其精确度预测系统。该系统使用了文中提出的基于图的选择算法。该系统的数据预处理模块也适用于其它TagSNP位点选择算法的前期数据处理。