发信人: yuelushan (朝闻夕死), 信区: Biology
标 题: 有趣的计算生物学问题(2)：标签序列设计问题
发信站: The unknown SPACE (Sat Aug 5 17:34:25 2000) WWW-POST

[问题] 考虑由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字符串)，每个包含两部份
：
一部份是事先设计好的tag序列，另一部份是特征的SNP序列，两者串
列在一起。
例如，我们希望鉴定一个SNP是这样的：

CGTGCTCGCTCTAaCTTTCGGCCGCCT
CGTGCTCGCTCTAtCTTTCGGCCGCCT

有一个位置可能为t,也可能为a(在某些个体上是t,另一些上是a);
我们设计一个特定针对这个SNP的标签序列CTGCAGCCG，那么
在溶液中就要合成两种分子，
序列分别是CGTGCTCGCTCTAaCTTTCGGCCGCCTCTGCAGCCG和
CGTGCTCGCTCTAtCTTTCGGCCGCCTCTGCAGCCG。合成时用不同的
染料标记上述两种分子。如果要同时鉴定N个SNP，那么需要合成
2*N个分子，设计N个不同的标签分子。

(2)制作基因芯片(参见上贴)，每个样孔中合成的序列恰好是设计的
tag序列的Watson-Crick互补链，则鉴定N个SNP，需要N个样孔。

(3)将待鉴定的个体基因样品加工后与溶液里的DNA片段杂交，然后
分离匹配的双链DNA。由于实验条件控制得当，只有与此样品完全匹
配的
那种SNP片段(2个中的1个)才会留下来，可以想象此时的DNA是这样的
：
<--- SNP ----><--tag-->
------------------------
---------------
SNP部份形成双链，tag部份仍是单链。

(4)将这些样品与芯片杂交，tag/antitag将结合在一起。因为我们事
先
知道每种tag对应的SNP种类，然后再检测每个样孔对应的染色，就可
以
自动的分析出每种SNP的类型。

开头的问题是关于tag/antitag的设计。上述过程中最为关键的是tag
/antitag的杂
交。我们只希望我们设计好的对才会匹配，否则会有噪音干扰结果。
根据简单的2-4规则，在杂交实验中A-T匹配的自由能约为G-C配对的
一半。
我们希望设计好的配对，其自由能均大于H，而其它的配对均小于C。
当且仅当，两个tag序列包含同样的子序列，其与anti-tag的匹配
自由能大于C时，才会出现交叉匹配。如此则回到我们开始提出的问
题。

[算法思路] 1. 基于环形序列的设计；
2. 考虑de bruijn图。




--
※ 来源:．The unknown SPACE bbs.mit.edu．[FROM: hto-pc13.usc.ed]