最大节约原则下单倍型推导问题的实用算法

• 作者: 孙广中 张强锋 车皓阳 陈国良
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 基因型 单倍型 SNP 单倍型推导 最大节约原则 贪心算法
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1699-1707
• 页数: 9页
• 分类号: TP301
• 语种: 中文

摘要

在疾病的易感基因研究和药物反应实验中,常常需要知道单倍型,而不仅仅是基因型数据.但是直接通过生物学实验手段来测定单倍型在时间和成本上消耗过大,所以在实验室里往往仅测得基因型,而通过一些计算手段来推导出单倍型.不同于Clark著名的单倍型推导模型,Gusfield和Wang等人提出了一种通过基因型样本推导单倍型的新模型.这种模型试图按照最大节约原则去寻找可以解释基因型样本的最小单倍型集合.这种基于节约原则的模型克服了Clark模型的一些缺陷.提出了节约原则模型的一个多项式时间的贪心算法以及一种把贪心策略和分支限界策略集合在统一框架下的复合算法.相对于Wang原来提出的分支限界完全算法,贪心的近似算法运行快得多,而且同时保持了比较准确的推导结果.新的复合算法也是一种完全算法.实验结果表明,与原来的分支限界算法相比,复合算法可以极大地提高运行效率以及可应用的实例规模.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学技术系	123	2142	20.0	43.0
2	孙广中	中国科学技术大学计算机科学技术系	34	328	8.0	17.0
3	张强锋	中国科学技术大学计算机科学技术系	3	10	2.0	3.0
4	车皓阳	中国科学院软件研究所	4	18	2.0	4.0