有趣的计算生物学问题(1)：基因芯片的设计# Biology - 生物学
y*n
1 楼
[问题] 给定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样孔
，
把它们排列到一个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样孔