Sequence alignment is a basic method in computational approach to analyze biological sequences. The importance and impact of the improvements in alignments is so great in bioinformatics that more fundamental and basic researches are required.
The improvement of both pairwise alignment and multialignment algorithms have been tried in this thesis. An application algorithm using automata in biological sequence pattern recognition and a new filtering algorithm used in contig assembly program have been developed. And a promoter search algorithm has been developed to implement a practical application system.
A new pairwise algorithm using linear space is faster than the commonly used Myers and Miller’s algorithm and it is expected that the algorithm could replace it, though in theoretical aspect, more accurate investigation should be done to analyze algorithmic complexity.
A new multialignment algorithm uses very different approach from conventional progressive multialignment algorithms. It also uses its own unique data structures. Though the effect could be proved through effective implementation, it is expected that the algorithm could replace the current algorithms because it will overcome many defects of the conventional algorithms.
Search algorithms of biological sequences patterns using automata showed good running time efficiency compared with those of general search methods. Such application will be useful for motif pattern recognition and other exact pattern searches. A new filter algorithm using dimer frequency increased the total efficiency of contig assembly program by rapidly and selectively filtering non-overlapping fragments with a high fidelity.
A promoter search algorithm was implemented to a practical program running on UNIX. The usefulness and promise were proved through a case study with bacterial classIII promoters. Two genes b2737 and ppdA captured by the promoter search program were proved to be related with $\acute{o}^F$ control, through beta galactosidase assay. Windows version will be implemented as a user-friendly program.
Further studies on theoretical analysis and implementation of the developed algorithms will show clearer impact of the current works as new research problems.
서열정렬은 생물서열 정보를 분석하기 위한 계산에서 가장 기본적으로 사용되는 방법이다. 정렬 알고리즘의 개선이 생물정보학에 미치는 파급효과는 매우 크기 때문에 보다 근본적이고 기본적인 연구가 절실히 필요하다.
이 논문에서는 서열쌍 정렬 알고리즘과 다중서열정렬 알고리즘을 각각 개선하기 위한 알고리즘이 하나씩 시도되었다. 생물서열의 패턴 인식을 위해 automata를 사용하는 알고리즘과 contig 조립 프로그램에서 사용되는 새로운 필터링 알고리즘도 개발하였다. 프로모터 검색 알고리즘을 개발하여 실제적인 문제를 해결하기 위한 시스템으로 구성하였다.
선형 공간을 사용하는 서열쌍 정렬의 새로운 알고리즘은 기존의 Myers와 Miller의 선형 공간 알고리즘보다 빨라서 이를 대치할 것으로 기대한다. 한편으로는 이 알고리즘의 복잡도를 보다 정확히 분석하기 위한 이론적인 연구가 더 진행되어야 할 것이다.
새로 개발된 다중서열정렬 알고리즘은 기존의 점진적 다중정렬 방식과는 매우 다른 접근방식을 사용한다. 효과적인 구현을 통해 그 유효성이 검증되어야 하지만, 이 알고리즘은 기존 방식의 많은 단점을 극복할 것이므로 현재의 방식을 대체하게 될 것이다.
Automat를 사용해서 생물서열의 패턴을 검색하는 방식은 일반적인 패턴 검색에 비해 대단히 빠른 효율을 나타낸다. 이 방식은 motif 검색이나 다른 정확한 패턴의 검색에도 유용하게 사용될 수 있을 것이다. 새로 개발된 필터링 알고리즘은 dimer 빈도를 이용하는 것으로 contig 조립에서 겹칠 수 있는 단편서열의 쌍들을 신속하고 정확하게 찾아주므로 전체적인 시간을 매우 향상시킨다.
개발된 프로모터 검색 알고리즘은 UNIX 프로그램으로 구현되었다. 박테리아의 classIII 프로모터로 분석한 사례연구분석을 통해 이 프로그램의 유용성과 전망이 검증되었다. Beta galactosidase 분석을 통해 $\acute{o}^F$ 제어와 관련된 새로운 유전자 b2737과 ppdA 가 이 프로그램을 통해 발견되었다. 이 프로그램은 사용자 편의를 갖춘 Windows 프로그램으로도 구현될 것이다.
개발된 알고리즘들에 대한 구현과 이론적인 부분의 후속연구를 통해 본 논문의 일들이 가지는 효과가 더욱 명확해 질 것이며 이러한 일들은 또 다른 새로운 일이 될 것이다.
