---

金－４　ゲノム情報に特化したパターン照合アルゴリズムに関する研究

ゲノム情報はＡ，Ｔ，Ｃ，Ｇのたった４つのヌクレオチドの並びによって表現される． この研究では，４つの記号のみからなる特殊な場合のパターン照合に適した アルゴリズムの提案と検証を行なう．パターンとテキストは，完全に一致していなくても よく，ユーザの与えるパラメタによって指定される類似度以上のものを検索(相同性検索)する必要がある． 現在は，Smith-Waterman法に前処理を組み合わせた手法を開発中であり，この改善を目指す．

• 前処理の効率化，高速化
  Smith-Waterman法は，時間がかかる手順であるため，パターンとテキストに現れる各文字の 出現頻度から，指定される類似度を超える可能性のないテキストに対しては，Smith-Waterman法を 適用しないようにしている．この前処理を工夫し，さらに効率を上げたり，速度を上げたりする．
  
  
• Smith-Waterman法の高速化
  Smith-Waterman法は，パターンとテキストの一部を添え字とする大規模な行列に対して，その 要素を境界条件から求める．そのため，Smith-Waterman法の実行には，大きな時間が必要と なっている．そこで，手法全体の速度を支配するSmith-Waterman法の高速化をはかり，一気に 手法の実行速度の改善を目指す．
  
  
• 後処理の効率化
  後処理を導入し，Smith-Waterman法の結果から，類似度を越える可能性のないテキスト列を スキップし，次にチェックすべきテキスト部分列を効率的に見つけるような仕組みを目指す．
  
  
• 処理の並列化
  並列処理を導入し，相同性検索を高速に実施する．具体的には，前処理を通過した部分文字列を 並列に処理する；Smith-Waterman法に対する並列処理手法を工夫する；GPGPUを活用する；などの アプローチで高速化を目指す．

---

塩基配列がきちんと読めているとは限らないので１文字分落ちていることもある． それでも照合できるようなアルゴリズムでないと使い物にならない．

---

金－４　最近の研究成果

新しい分野を切り拓いているため，発表数はあまりありません．今年は，研究成果を世界に向けて発信する予定です．皆さんの活躍の余地が大いにあります．

• Tamura, Kenya, and Keiichi Kaneko: "Acceleration of a Parallel Homology Search for Base Sequences by a GPU," Proceedings of the 2017 Sixth ICT International Student Project Conference, Johor Bahru, Malaysia, May 23--24, 2017.(修士研究)
• 佐藤暁, 平井佑樹, 金子敬一: "相同性検索の効率的な並列化手法," 電子情報通信学会総合大会論文集, 岐阜大学, Mar. 19-22, 2013.(修士研究)
• 加瀬友晴, 金子敬一: "アミノ酸配列における近似パタン検索アルゴリズムに関する研究," 電子情報通信学会総合大会論文集, D-1-7, p. 7, 北九州学術研究都市, Mar. 18--21, 2008.(修士研究)
• 加瀬友晴, 斉藤理, 金子敬一: "塩基配列の局所的な類似文字列検索アルゴリズム," 電子情報通信学会総合大会論文集, D-1-6, p. 6, 名城大学, Mar. 20--23, 2007.(卒業研究)