Title :
An Improved Quick Algorithm for Aligning DNA/RNA Sequences
Author :
Zou, Quan ; Guo, Maozu ; Liu, Yang ; Zhang, Taotao
Author_Institution :
Harbin Inst. of Technol., Harbin
Abstract :
Biology sequence database search is an important problem for bioinformatics research. The main search software BLAST is based on the BYP algorithm. In BYP, if the length of hit region is set long, it may lose similar appearance. Otherwise, there may be too many r-length regions from Aho-Corasik algorithm. Checking where exists any approximate alignments for the DNA or RNA sequence always spends much time, although the expected running time of BYP is linear. A new algorithm is proposed from the viewpoint of shorting the length and increasing the number of the regions, which can make most of the false r-length regions excluded. Thus the algorithm can align the DNA or RNA sequences quickly since the rate of real r- length regions is increased. Experimental results show that the proposed algorithm is computational efficient and achieves good performance.
Keywords :
DNA; biology computing; molecular biophysics; Aho-Corasik algorithm; BYP algorithm; DNA sequence; RNA sequence; bioinformatics; biology sequence database search; search software BLAST; Biology computing; Computational biology; Computational intelligence; DNA; Dynamic programming; Heuristic algorithms; Hidden Markov models; Partitioning algorithms; RNA; Sequences;
Conference_Titel :
Computational Intelligence and Security Workshops, 2007. CISW 2007. International Conference on
Conference_Location :
Harbin
Print_ISBN :
978-0-7695-3073-4
DOI :
10.1109/CISW.2007.4425622