ゲノム解析に用いるDPマッチングの分割統治法による高速化

• 中川, 匠

• 吉原, 郁夫

• 山森, 一人

• 安永, 守利

• Nakagawa, Takumi

書誌事項

タイトル別名

• A Divide-and-Conquer Method of Dynamic Programming for Genome Informatics
• ゲノム カイセキ ニ モチイル DP マッチング ノ ブンカツ トウチホウ ニ ヨル コウソクカ

抄録

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.

収録刊行物

• 宮崎大学工学部紀要

  宮崎大学工学部紀要 35 257-262, 2006-08-30

  宮崎大学工学部

キーワード

• Genome Informatics, Dynamic Programming, Divide-and-Conquer, Alignment, Feature Extraction

詳細情報

• CRID: 1050570264722509568
• NII論文ID: 110005001914
• NII書誌ID: AA00732558
• ISSN: 05404924
• HANDLE: 10458/445
• NDL書誌ID: 8568643
• Web Site: https://miyazaki-u.repo.nii.ac.jp/records/2480
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I8568643
• 本文言語コード: ja
• 資料種別: departmental bulletin paper
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN