DSC : Efficient Primer design algorithm with partial order graphs
Yu-Cheng Huang1, Ming-Hui Jin 2, Cheng-Yan Kao
1r91021@csie.ntu.edu.tw, NTU. Computer Science and Information Engineering Department; 2jinmh@db.csie.ntu.edu.tw, Bioinformatics Research Center, National Taiwan University, Taiwan
A novel method called DSC (Difference String Comparison) is proposed for speeding up the primer finding procedure. Since the DNA sequence under investigation is then amplified by PCR (polymerase chain reaction) with primers specific for bisulfite-modified DNA (Clark et al. 1994), an efficient primer finding mechanism is helpful for the genomic researches.
Since the finding primer processes are based on sequence comparison, to provide competent primer finding tools, several efficient sequence comparison algorithms were proposed. However, their approaches ignore that the primer finding time could be further reduced through presenting the DNA sequences with different format.
DSC divides the primer finding procedure into two steps. First, DSC presents DNA sequences as a partially ordered graph in which individual sequence letters are represented by nodes, and directed edges are drawn between consecutive letters in each sequence. Then DSC merges all sequences into a compact graph when the sequences have identical letter at the same position. The compact graph reserves all information of sequences and hence reduces the storage space. Second, DSC applies the compact graph to do string matching with criteria including the proximity between primer melting temperatures, minimization of hybridization effects between forward and reverse primers, and avoidance of hybridization of primers with themselves. The last two criteria are dealt with by annealing values. DSC can make use of the compact graph and slash the duplicate computation.
DSC speeds up the process of primer design and reduces the storage space for maintaining the DNA sequences. DSC is also appropriate for other domains, which need sequence comparison like motif-finding, probe design … etc.