Research

Algorithms


□ 연구내용

  • 대용량의 텍스트에 대한 인덱스 자료 구조 생성 알고리즘 연구
  • 인덱스 자료구조를 이용한 효율적인 패턴 검색 알고리즘 연구
  • 근사문자열 알고리즘 연구

  • □ 주요연구성과

  • 선형시간 접미사트리(suffix tree) 및 접미사배열(suffix array) 생성 알고리즘 개발
  • 선형시간 접미사 배열 탐색 알고리즘 개발


  • Complexity Theory


    □ 연구내용

  • 컴퓨터로 풀 수 있는 문제와 없는 문제에 대한 연구
  • 컴퓨터로 빠른 시간 내에 풀기 어려운 문제들에 대한 연구

  • □ 주요연구성과

  • 다중 서열 배치(multiple sequence alignment) 문제의 NP-완전 증명
  • 근사주기, 근사커버 문제의 NP-완전 증명

  • Application - Bioinformatics


    □ 연구내용

  • DNA 등 유전체 서열을 분석하여 중요한 정보를 추출하는 연구

  • □ 주요연구성과

  • 접미사배열과 근사문자열 매칭 알고리즘을 이용한 전사인자 결합부위 예측 프로그램 개발