摘要
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2~kn^2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k_1-1)k_22^(2h)+(k_1+1)^(2h)+nk_2+mk_1)的新算法,其中,k_1为一个片断覆盖的最大SNP位点数(不大于n),k_2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k_2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.
The individual haplotyping MSR （minimum SNP removal） problem is the computational problem of inducing an individual＇s haplotypes from one＇s DNA fragments sequencing data by dropping minimum SNPs （single-nucleotide polymorphisms）. To solve the problem, Bafna, et al. had provided an algorithm of time complexity o（2^kn^2m） with the number of fragments m, the SNP sites n, the maximum number of holes k in a fragment. In the case that there are some Mate-Pairs, since the number of holes in a Mate-Pair can reach 100, Bafna＇s algorithm is impracticable. Based on the characters of DNA fragments, this paper presents a new algorithm of time complexity O（（n-1）（k1-1）k22^2h＋（k1＋1）2h＋nk2＋mkl） with the maximum number of SNP sites that a fragment covers kl （no more than n）, the maximum number of the fragments covering a SNP site k2 （usually no more than 19） and the maximum number of fragments covering a SNP site whose value is unknown at the SNP site h （no more than k2）. Since the time complexity is not directly related with k, the algorithm can deal with the MSR problem with Mate-Pairs efficiently, and is more scalable and applicable in practice.
出处
《软件学报》
EI
CSCD
北大核心
2007年第9期2070-2082,共13页
Journal of Software
基金
Supported by the National Natural Science Foundation of China under Grant No.60433020(国家自然科学基金)
the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683(新世纪优秀人才支持计划)
the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No.IRT0661(国家教育部创新团队资助项目)
the Scientific Research Fund of Hunan Provincial Education Department of China under Grant No.06C52(湖南省教育厅资助科研项目)
