Genomics Inform Search


Genomics Inform > Volume 1(1); 2003 > Article
A Heuristic Algorithm to Find All Normalized Local Alignments Above Threshold.
Sangtae Kim, Jeong Seop Sim, Heejin Park, Kunsoo Park, Hyunseok Park, Jeong Sun Seo
1Department of Computer Science, Korea Military Academy, Seoul, Korea.
2Electronics and Telecommunications Research Institute, Daejeon, Korea.
3School of Computer Science and Engineering, Seoul National University, Seoul, Korea.
4Institute of Bioinformatics, Macrogen, Inc., Seoul, Korea.
5Department of Computer Science, Ewha Womans University, Seoul, Korea.
6Ilcheon Molecular Medicine Institute, Seoul National University, Seoul, Korea.
Local alignment is an important task in molecular biology to see if two sequences contain regions that are similar. The most popular approach to local alignment is the use of dynamic programming due to Smith and Waterman, but the alignment reported by the Smith-Waterman algorithm has some undesirable properties. The recent approach to fix these problems is to use the notion of normalized scores for local alignments by Arslan, Egecioglu and Pevzner. In this paper we consider the problem of finding all local alignments whose normalized scores are above a given threshold, and present a fast heuristic algorithm. Our algorithm is 180-330 times faster than Arslan et al.''s for sequences of length about 120 kbp and about 40-50 times faster for sequences of length about 30 kbp.
Keywords: local alignment; dynamic programming; normalized score; fractional programming
Share :
Facebook Twitter Linked In Google+
METRICS Graph View
  • 286 View
  • 4 Download
Related articles in GNI


Browse all articles >

Editorial Office
Rm.1011, The Korea Science & Technology Center, 22, Teheran-ro, 7-gil, Gangnam-gu, Seoul, 06130, Korea
Tel: +82-2-558-9394    Fax: +82-2-558-9434    E-mail:                

Copyright © 2019 by Korea Genome Organization. All rights reserved.

Developed in M2community

Close layer
prev next