Parallel Algorithms for DNA Probe Placement on Small Oligonucleotide Arrays
Parallel Algorithms for DNA Probe Placement on Small Oligonucleotide Arrays
复制标题
在小型寡核苷酸阵列上放置 DNA 探针的并行算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S. Rajasekaran
中科院分区：
文献类型：
--
作者：
D. Trinca;S. Rajasekaran
寡核苷酸阵列广泛应用于基因组分析，如基因表达谱分析、比较基因组杂交、染色质免疫沉淀、SNP检测等。在制造过程中，选择性地将寡核苷酸阵列的位点暴露在光下，以激活寡核苷酸以进一步合成。光学效果会在有意暴露于光下的位置相邻的被遮蔽的位置造成不必要的照明。这导致在屏蔽位点合成不可预见的序列，并危及实验数据的解释。为了减少这种不确定性，人们可以利用探针如何分配到阵列位置的自由。边界长度最小化问题（BLMP）寻求最小化所有掩模中边界长度总和的探针放置。在本文中，我们提出了两个并行的BLMP算法。所提出的并行算法以局部搜索范式为核心，并专门为BLMP开发。结果表明，对于最多1156个探针的小型微阵列，所提出的并行算法的性能优于现有的最佳算法。
Oligonucleotide arrays are used in a wide range of genomic analyses, such as gene expression profiling, comparative genomic hybridization, chromatin immunoprecipitation, SNP detection, etc. During fabrication, the sites of an oligonucleotide array are selectively exposed to light in order to activate oligonucleotides for further synthesis. Optical effects can cause unwanted illumination at masked sites that are adjacent to the sites intentionally exposed to light. This results in synthesis of unforeseen sequences in masked sites and compromises interpretation of experimental data. To reduce such uncertainty, one can exploit freedom in how probes are assigned to array sites. The border length minimization problem (BLMP) seeks a placement of probes that minimizes the sum of border lengths in all masks. In this paper, we propose two parallel algorithms for the BLMP. The proposed parallel algorithms have the local-search paradigm at their core, and are especially developed for the BLMP. The results reported show that, for small microarrays with at most 1156 probes, the proposed parallel algorithms perform better than the best previous algorithms.