有趣的计算生物学问题(2)：标签序列设计问题# Biology - 生物学
y*n
1 楼
[问题] 考虑由A，C，G，T组成的字符串s=a1a2...ak,定义s的权值
为W(s)=sum(w(ai)),其中w(A)=w(T)=1,W(C)=W(G)=2.给定两个参数
c和h(h>c),我们称一组字符串是一组c-h码，如果它们满足下面两个
条件：
(1)其中每个字符串的权值大于h;
(2)只包括任何权值大于c的子串至多一次。
问(1)满足什么条件的c,h才可能有c-h码的解。
(2)给定c和h,如何找到最大的一个c-h码(包含最多字符串)。
[背景]人基因组上存在着一些所谓单核甘酸多态性(single
nucleotide
polymophism)的位点，这些位点上的核甘酸(ACTG之一)在人与人
之间是不一样的。粗略的估计，这些位点大约占整个基因组的0.1%.
根据SNP可以快速的进行基因型鉴定(genotyping)，因为基因型的
差异必然是SNP的一种。假定我们已经发现了所有的SNP，利用基因
芯片就可以进行快速的genotyping。这就是SNP TAT(tag/antitag)
系统。具体步骤是这样：
(1)在溶液中合成一些DNA片段(可看作ACTG字符串)，每个
为W(s)=sum(w(ai)),其中w(A)=w(T)=1,W(C)=W(G)=2.给定两个参数
c和h(h>c),我们称一组字符串是一组c-h码，如果它们满足下面两个
条件：
(1)其中每个字符串的权值大于h;
(2)只包括任何权值大于c的子串至多一次。
问(1)满足什么条件的c,h才可能有c-h码的解。
(2)给定c和h,如何找到最大的一个c-h码(包含最多字符串)。
[背景]人基因组上存在着一些所谓单核甘酸多态性(single
nucleotide
polymophism)的位点，这些位点上的核甘酸(ACTG之一)在人与人
之间是不一样的。粗略的估计，这些位点大约占整个基因组的0.1%.
根据SNP可以快速的进行基因型鉴定(genotyping)，因为基因型的
差异必然是SNP的一种。假定我们已经发现了所有的SNP，利用基因
芯片就可以进行快速的genotyping。这就是SNP TAT(tag/antitag)
系统。具体步骤是这样：
(1)在溶液中合成一些DNA片段(可看作ACTG字符串)，每个