单核苷酸多态性(SNPs,Single Nucleotide Polymorphisms)研究是目前生物信息学领域中的重要课题之一。2000年人类全基因组草图的完成和2003年人类全基因组序列测定的彻底完成,极大地促进了生命科学家对于人类个体基因组序列中包含遗传信息的研究以及与人类各种个体表现特征相关基因组序列片段识别的研究。越来越多的生物信息学研究人员致力于从已有的遗传序列数据中挖掘包含遗传差异信息的遗传标记位点,分析各位点间遗传联系与差异并将其应用于疾病关联性研究中。SNP位点作为重要的遗传标记之一,其相关分析方法及其应用更受到了广泛关注。由于SNP位点数目巨大,使用现有计算方法进行分析通常面临着效率较低,花费较大等缺憾。因此,本文从SNP位点的固有特性出发,结合机器学习方法与图论知识,对单核苷酸多态性研究中的若干关键问题进行深入的研究。本文的主要内容包括:(1)提出基于参数过滤和集成学习的EST序列集SNP位点挖掘方法。通过生物手段获取和验证SNP位点花费巨大,而目前已有的挖掘算法通常面临着假阳性高及不能应用于非同类数据等问题。本文结合SNP位点固有特性构造过滤器,对表达序列标签(expressed sequence tag,EST)数据中SNP候选位点进行筛选,并针对SNP位点挖掘中训练集中正反例不平衡的问题,首先定义并筛选了一组有效特征,再结合集成学习和AdaBoost思想,通过切分重构正反例平衡的训练集,使用多分类器训练并采取合理的投票机制从过滤后的SNP候选集中挖掘SNP位点。与现有挖掘方法相比,本文算法特异性和敏感性均超过80%,获取的SNP位点正确率更高,能够极大地降低伪SNP位点的获取概率,有效降低了假阳性,实验结果表明本算法同样适用于缺少基因组数据的物种的SNP挖掘,有助于降低生物实验花费。(2)提出基于图模型和聚类算法的标签SNP位点挖掘方法。直接使用从EST序列集中挖掘出的的海量SNP位点进行相关研究需要花费大量的时间和金钱,因此出现了大量提取具有代表性的标签SNP位点的计算方法。针对现有方法信息缺失,限制条件较多等问题,本文首次提出了使用SNP位点图来描述各SNP位点间连锁不均衡性和遗传差异性,并结合信息论方法,通过基于最大密度子图和信息熵的图算法获取标签SNP位点。基于这种图算法,本文分别针对单体型序列和基因型序列数据提出标签SNP位点获取算法。此外,本文引入K近邻思想进行数据预处理,能够有效降低处理海量数据时图算法的复杂度。实验验证本文算法能够降低获取过程中的遗传信息缺失,提高了标签SNP位点获取精确度。(3)结合本文中挖掘SNP位点、获取标签SNP位点取得的结果,提出了基于信息论和层次聚类算法的人群结构推断方法。人群结构推断是单核苷酸多态性分析中的重要问题之一。本文首次将标签SNP位点作为人群结构推断中的重要特征,通过基于图的特征选择算法,减小基因型序列数据维数,降低噪声和无效SNP位点对推断精度的影响。通过构造基因型序列转换函数将序列遗传距离与序列间转化信息熵相结合,提出了一种新型的基于层次聚类的人群结构推断算法。将本文方法分别应用于模拟数据和人类真实数据上均取得了较好的效果。此外,将特征选择算法获取的标签SNP位点应用于现有的人群结构推断算法上也取得了很好的效果,在降低了已有算法推断时间的同时更提高了其推断精度。(4)结合本文前阶段单核苷酸多态性各类分析算法的成果,提出了基于人类线粒体SNP(mtSNPs)的疾病人群分类方法。单核苷酸多态性分析的最终目的是为了进行疾病关联性研究。疾病人群分类作为疾病关联性研究的重要问题之一受到了越来越多的关注。相比于目前的分类方法,本文将线粒体DNA序列作为研究对象,使用了基于关键字树的序列比对算法对线粒体DNA序列进行有效对齐。结合SNP特征分析结果,从比对后线粒体DNA序列中获取SNP位点。在此基础上,结合人群结构推断算法,对线粒体SNP位点集内疾病不相关SNP位点进行筛除,并提出了基于统计显著性的疾病关联线粒体SNP定位算法。最后,将获取的疾病关联线粒体SNP作为特征应用于有效的分类方法中进行疾病人群分类。在真实疾病人群数据上的实验结果证明了本文方法的有效性。此外,显著性SNP及其获取算法也可以用于其它疾病分类及关联性问题研究中。