2 種類のモチーフ検索問題に対する厳密解法－ワイルドカードを許す問題と編集距離を用いる問題Exact algorithms for two variants of the planted motif search problem - the problem with wildcards permitted and the problem based on an edit distance

摘要

モチーフ検索問題(planted motif search problem) は，生物学と情報科学の融合分野であるバイオインフォマティクスにおいて研究される問題の一つであり，DNA 塩基配列やアミノ酸配列などに代表される複数の文字列に共通して出現する，モチーフとよばれる部分文字列を検索する問題である．ここでモチーフとは，生物学的には，特定の機能に関わる部分に共通して出現する短い配列を指すが，実際には，変異により少しずつ異なった形で出現することになる．したがって，出現した配列(以降では，出現(occurrence) とよぶ) を代表する配列がモチーフである，といえる．そこで，モチーフ検索問題では，類似した出現が各文字列に含まれるようなモチーフを求めることを目的とする．このようなモチーフ検索問題に対する研究はこれまで盛hに行われてきたが，その多くは，モチーフとその出現の類似度をはかる尺度としてハミング距離(同じ長さの文字列の中で文字が一致しない数，例えばTTGACA とTAGACA のハミング距離は1 である) を用いていた．本研究では，より一般化したモチーフ検索問題として，(1) ハミング距離を用いるがワイルドカードを許す場合，および(2) 編集距離を用いる場合，におけるモチーフ検索問題を考え，これらの問題に対する厳密解法を提案する．さらに，数値実験により提案解法の有効性を検証する．