計算困難な問題への混成アプローチ:近似、並列化、randomization

まず、計算的分子生物学における基本的な問題の一つである入れ子構造の弧付き最長共通部分列問題について研究した。この問題は1999年、米国のVictoria大学のEvans博士がtRNAと蛋白質の二次構造解明の研究で定式化された。Evans博士がこの問題のNP-困難性を推測したが、未解決のままにした。そのNP-困難性は本研究で初めて証明された。また、この問題の実用性のため、本研究でこの問題を解くための近似アルゴリズムを二つ設計した。特に、その近似アルゴリズムの一つは入力の系列が「k-diagonal」という良く知られている性質を満たす場合、最適解にほしい分だけ近い近似解を見つけることができる(すなわち、多項式時間近似スキームである)。この近似アルゴリズムを効率よく並列化することもできる。次に、頂点が生物の種類に対応し、辺が生物間の近縁関係に対応するグラフが与えられたとき、生物の系統史(phylogeny)を再構築する問題について研究した。この問題も計算的生物学における基本的な問題の一つである。本研究で、各種類の生物が定数個の新しい種類の生物しか生まない場合、この問題を解く線形時間のアルゴリズムが存在することを示した。また、実験で得られる生物間の近縁関係にエラーが出やすいことから、エラーを考慮したときの生物系統史の再構築問題についても研究した。この問題がNP困難であることを示した。この問題に対する近似アルゴリズムの開発はこれからの課題である。

まず、計算的分子生物学における基本的な問題の一つである入れ子構造の弧付き最長共通部分列問題について研究した。この問題は1999年、米国のVictoria大学のEvans博士がtRNAと蛋白質の二次構造解明の研究で定式化された。Evans博士がこの問題のNP-困難性を推測したが、未解決のままにした。そのNP-困難性は本研究で初めて証明された。また、この問題の実用性のため、本研究でこの問題を解くための近似アルゴリズムを二つ設計した。特に、その近似アルゴリズムの一つは入力の系列が「k-diagonal」という良く知られている性質を満たす場合、最適解にほしい分だけ近い近似解を見つけることができる(すなわち、多項式時間近似スキームである)。この近似アルゴリズムを効率よく並列化することもできる。次に、頂点が生物の種類に対応し、辺が生物間の近縁関係に対応するグラフが与えられたとき、生物の系統史(phylogeny)を再構築する問題について研究した。この問題も計算的生物学における基本的な問題の一つである。本研究で、各種類の生物が定数個の新しい種類の生物しか生まない場合、この問題を解く線形時間のアルゴリズムが存在することを示した。また、実験で得られる生物間の近縁関係にエラーが出やすいことから、エラーを考慮したときの生物系統史の再構築問題についても研究した。この問題がNP困難であることを示した。この問題に対する近似アルゴリズムの開発はこれからの課題である。