CAJ | 학술논문

在疾病的易感基因研究和药物反应实验中,常常需要知道单倍型,而不仅仅是基因型数据.但是直接通过生物学实验手段来测定单倍型在时间和成本上消耗过大,所以在实验室里往往仅测得基因型,而通过一些计算手段来推导出单倍型.不同于Clark著名的单倍型推导模型,Gusfield和Wang等人提出了一种通过基因型样本推导单倍型的新模型.这种模型试图按照最大节约原则去寻找可以解释基因型样本的最小单倍型集合.这种基于节约原则的模型克服了Clark模型的一些缺陷.提出了节约原则模型的一个多项式时间的贪心算法以及一种把贪心策略和分支限界策略集合在统一框架下的复合算法.相对于Wang原来提出的分支限界完全算法,贪心的近似算法运行快得多,而且同时保持了比较准确的推导结果.新的复合算法也是一种完全算法.实验结果表明,与原来的分支限界算法相比,复合算法可以极大地提高运行效率以及可应用的实例规模.
재질병적역감기인연구화약물반응실험중,상상수요지도단배형,이불부부시기인형수거.단시직접통과생물학실험수단래측정단배형재시간화성본상소모과대,소이재실험실리왕왕부측득기인형,이통과일사계산수단래추도출단배형.불동우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.