主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张强锋,车皓阳,陈国良,孙广中.最大节约原则下单倍型推导问题的实用算法.软件学报,2005,16(10):1699-1707
最大节约原则下单倍型推导问题的实用算法
A Practical Algorithm for Haplotyping by Maximum Parsimony
投稿时间:2004-05-31  修订日期:2004-11-15
DOI:
中文关键词:  基因型  单倍型  SNP  单倍型推导  最大节约原则  贪心算法
英文关键词:genotype  haplotype  SNP  haplotyping  maximum parsimony  greedy algorithm
基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401(国家重点基础研究发展规划(973))
作者单位
张强锋 中国科学技术大学,计算机科学技术系,安徽,合肥,230027 
车皓阳 中国科学院,软件研究所,北京,100080 
陈国良 中国科学技术大学,计算机科学技术系,安徽,合肥,230027 
孙广中 中国科学技术大学,计算机科学技术系,安徽,合肥,230027 
摘要点击次数: 2823
全文下载次数: 2683
中文摘要:
      在疾病的易感基因研究和药物反应实验中,常常需要知道单倍型,而不仅仅是基因型数据.但是直接通过生物学实验手段来测定单倍型在时间和成本上消耗过大,所以在实验室里往往仅测得基因型,而通过一些计算手段来推导出单倍型.不同于Clark著名的单倍型推导模型,Gusfield和Wang等人提出了一种通过基因型样本推导单倍型的新模型.这种模型试图按照最大节约原则去寻找可以解释基因型样本的最小单倍型集合.这种基于节约原则的模型克服了Clark模型的一些缺陷.提出了节约原则模型的一个多项式时间的贪心算法以及一种把贪心策略和分支限界策略集合在统一框架下的复合算法.相对于Wang原来提出的分支限界完全算法,贪心的近似算法运行快得多,而且同时保持了比较准确的推导结果.新的复合算法也是一种完全算法.实验结果表明,与原来的分支限界算法相比,复合算法可以极大地提高运行效率以及可应用的实例规模.
英文摘要:
      Haplotypes, rather than genotypes are required in some disease susceptibilities and drug response tests.However, it is both time-consuming and expensive to obtain haplotypes experimentally. Therefore usually genotype data are collected in the laboratory at first, then, haplotype data are inferred from them resorting to some computational approaches. Different from Clark's well-known haplotype inference method, Gusfield and Wang et al.proposed a new model according to the maximum parsimony principle. It tries to find a minimum set of haplotypes that can explain the genotype samples. This parsimony model overcomes some weaknesses of Clark's method. For the parsimony this paper presents model a polynomial time greedy algorithm and a compound algorithm that combines the greedy policy with the branch-and-bound strategy in a uniform framework. Compared with the original complete algorithm proposed by Wang et al., the greedy approximation algorithm runs much faster, and in the meanwhile, produces relatively higher accurate results. The compound algorithm is also a complete algorithm.Simulation results show that it is much more efficient and can be applied to instances of much larger scales than the original complete algorithm.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利