An Algorithm to Select Target Specific Probes for DNA Chips
Motivation: The selection of target specific probes is a relevant problem in the design of DNA chips. Given a set S of genomic sequences, the task is to find at least one oligonucleotide, called probe, for each target sequence in S. This probe will be attached to the chip surface, and must be chosen in a way that it will not hybridize to any other sequence but the intended target. Furthermore, all probes on the chip must hybridize to their intended targets under the same reaction conditions, most importantly at the temperature T at which the experiment is conducted. Results: We present an efficient algorithm for the probe design problem. Melting temperatures are calculated for all possible probe-target interactions using an extended nearest-neighbor model, allowing for both non-Watson-Crick base-pairing and unpaired bases within a duplex. To compute temperatures efficiently, a combination of suffix trees and dynamic programming based alignment algorithms is introduced. Additional filtering steps during preprocessing increase the speed of the computation. Also, an algorithm to select the actual probes from the set of candidates is presented. The practicability of the algorithms is demonstrated by two case studies: The computation of probes for the identification of different HIV-1 subtypes, and finding probes for 28S rDNA sequences from over 400 organisms.
|Depositing User:||Lars Kaderali|
|Date Deposited:||16 Oct 2002 00:00|
|Last Modified:||16 Jan 2012 13:20|