发信人: yuelushan (朝闻夕死), 信区: Biology
标 题: 有趣的计算生物学问题(1)：基因芯片的设计
发信站: The unknown SPACE (Sat Aug 5 17:33:44 2000) WWW-POST

[问题] 给定N=m*n个相同长度的字符串(例如L=20)，欲找到一种算法
，
把它们排列到一个m*n的方阵上，使得所有相邻两个字符串的距离之
和最小。此处两个字符
串的距离定义为它们之间不同的字符位数，例如
dist(ABCDCGA,ABEDCAA) = 2.

[背景] Affymetrix生产的基因芯片基本原理是针对一个物种的每一
个基因(可以考虑成ACTG
组成的字符串)设计一组特定的引物(primer)(即一系列长度一定的字
符串)，然后在一块固
定大小的载体(如玻璃或尼龙)上并行合成这些引物。实验时把载体同
这种生物细胞中的mRNA
(或RT-PCR后的cDNA，经过染料修饰)杂交，根据每个引物杂交信号的
大小来推断各个基因在
细胞中的表达量。上述问题与Affymetrix的芯片合成技术有关。
考虑在2*2的方阵上合成如下设计好的引物，用1234来表示四个孔的
编号，
AC CC 1 2
AG GC 3 4
通过这样一个方案：
(1)在溶液中放核甘酸A，打开样孔1，3，这样，1，3样孔里就合成上
A：
A -
A -
(2)在溶液中放核甘酸G，打开样孔3，4，这样，3，4样孔里就合成上
G：
A -
AG G
(3)在溶液中放核甘酸C，打开样孔1，2，4，这样，1，2，4样孔里就
合成上C：
AC C
AG GC
(4)在溶液中放核甘酸C，打开样孔2，这样，2样孔里就合成上C：
AC CC
AG GC
整个合成就完成了。它可以通过一个编制好的程序由机器人自动来作
，只需设计好每步骤需
添加何种核甘酸(称为合成序列)，以及打开那些样孔就可以了。了解
计算机算法的朋友肯定
已经看出来了，给定m*n个引物序列，则最佳的合成序列应该是它们
的“最短一致覆盖序列
”(shortest common supersequence, SCS),也就是给n个字符串，找
一个最短字符串，使得
上述每个字符串是它的一个子序列(注意不是子串)，如上面的例子，
SCS(AC，CC，AG，GC)=AGCC。

SCS是一个NP问题(相关的有LCS，longest common sub-sequence).但
很容易估计SCS长度的
上界是L*sizeof(alphabet),例如上面例子里，L=2，alphabet共有3(
A，C，G)，故SCS<=6。

在开头给出的问题是这样引出的。在上述的合成过程中，每个合成过
程都要打开若干个样孔
，因为技术的限制，样空打开或关闭可能有一些误差，因此在样孔边
缘的合成可能是错误的
(即可能合成到临近的样孔中去)，故而我们希望在每个合成步骤里，
尽量打开邻近的样孔(
即使得打开样孔部份的周长最短)，以减小损失。如果我们假定采用
一种最简单的合成序列
：A，C，G，T，A，C，G，T，。。。 长度是引物长度的4倍(字母表
大小为4)，那么显然两
个相邻样孔(上下或左右相邻)的公共边被占用(即一边打开，一边关
闭)的次数为2倍它们之
间的距离。于是我们的芯片设计问题转化为开头所将的问题。

[基本算法方向]
(1) 分两步走：考虑一维排列(TSP问题)，再将结果“盘”到二维网
格上；
(2) 模拟算法。



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