A Divide-and-Conquer Method of Dynamic Programming for Genome Informatics

IR HANDLE Web Site

Bibliographic Information

Other Title
  • ゲノム解析に用いるDPマッチングの分割統治法による高速化
  • ゲノム カイセキ ニ モチイル DP マッチング ノ ブンカツ トウチホウ ニ ヨル コウソクカ

Search this article

Abstract

ABSTRACT Alignment based on DP-matching is used to extract unknown feature pattern embedd ed in genome sequence. To extract feature pattem with base length n, complete set of similarity of c andidate pattern with base length N = 2, 3, ・ ・ ・ , n is required. When extending base length n, number of candidate pattern and execution time i ncrease exponential order O(4n+1 ). This paper propose a new faster method of extracting feature pattern by reusing similartiy which is calculated past step. The method enable extracting feature pattern with base length n = 10 to speed up as much as 9 times than conventional method.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top