基因芯片是将被称为探针的DNA片段按照一定的顺序排列在固相支持物上构成的高密度探针阵列,根据核酸杂交原理,在适宜的条件下探针就会与特定的核酸序列杂交,基于这个特性,基因芯片就可以用来对给定样品中的核酸序列信息进行检测。它能够同时分析数以万计的基因组信息,具有重大的基础研究价值和明显的产业化前景。 探针选择和芯片优化是基因芯片设计过程中需要解决的两个主要问题。 探针选择的任务是为给定基因组中的目的基因选择特异性的探针,该探针必须能够将目的基因和非目的基因区分开,也就是说,在相同的杂交条件下,芯片上的探针只与目的基因杂交,而不与非目的基因杂交。由于基因组数据量很大,候选探针数目很多,这给探针选择带来了困难。本文给出了一个完整的探针选择算法,为了减少探针选择过程中的计算量,提出了一种新的探针特异性预测准则——Markov概率准则,在探针选择过程中,首先利用该准则对探针的特异性进行预测,然后选择那些特异性可能大的探针进行杂交温度计算,从而减少了进行计算的探针数量。在探针选择过程中,还利用Suffix Array数据结构对计算量进行削减。通过对HIV-1 subtypes的测试显示,探针选择过程中需要计算的探针数目减少到候选探针数目的1/10,这充分说明了算法的有效性。 掩膜板在高密度基因芯片的探针合成过程中起着重要的作用,由于其制造工艺复杂、造价较高,因此在不改变探针合成结果的条件下,应该尽可能的减少基因芯片探针合成过程中所用的掩膜板数量,降低芯片制造成本。本文提出了一种基于预测搜索的优化算法,利用该方法对掩膜板进行了优化设计,测试结果显示,其减少的掩膜板数量超过了传统方法的20%。