欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
个体单体型MSR（minimumSNPremoval）问题是指如何利用个体的基因测序片断数据去掉最少的SNP（single—nucleotidepolymorphisms）位点，以确定该个体单体型的计算问题对此问题，Bafna等人提出了时间复杂度为O（2^kn^2m）的算法，其中，m为DNA片断总数，n为SNP位点总数，k为片断中洞（片断中的空值位点）的个数由于一个Mate—Pair片段中洞的个数可以达到100，因此，在片段数据中有Mate—Pair的情况下，Bafna的算法通常是不可行的．根据片段数据的特点提出了一个时间复杂度为D（n-1）（足广1）k22^2k＋（k1＋1）^2k＋nk2＋mkl）的新算法，其中，k1为一个片断覆盖的最大SNP位点数（不大于n），k2也为覆盖同一SNP位点的片段的最大数（通常不大于19），h为覆盖同一SNP位点且在该位点取空值的片断的最大数（不大于也）．该算法的时间复杂度与片断中洞的个数的最大值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.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：