東北大学 大学院農学研究科・農学部

海洋生命遺伝情報学分野

計算問題を解くことの困難さ（あるいは容易さ）を理論的に解析する学問です。

例えば、同じ桁数の $2$ つの自然数同士を足し算するのと掛け算するのでは、どちらの計算がより難しいでしょう。算数ドリルで筆算をひたすらやらされた小学校当時のことを思い出すと、掛け算が難しいとの印象をもっている人が大半ではないでしょうか。でも、どのくらい難しい？と問われたら返答に少し困ってしまうかもしれません。

計算問題を解くための手順のことをアルゴリズムと呼びます。例えば、足し算や掛け算の筆算はアルゴリズムです。これらのアルゴリズムは、問題の具体例として $42588$ と $51343$ のような $5$ 桁の自然数を与えられると、小学校で教わったあの手順を実行することでそれぞれ和 $93931$ や積 $2186595684$ を求めます。足し算や掛け算のアルゴリズムの計算時間に関する性能は、問題の具体例として与えられる $2$ つの自然数の共通の桁数 $n$ に対して、最悪の場合に答えが得られるまでにかかる時間 $t(n)$ を見積もることで評価します。ただし、$t(n)$ を厳密に見積もることは意義に対して労力が大きすぎる場合が多いので、$t(n)$ が $f(n)$ に比例する値以下、以上、あるいはその両方であるような $f(n)$ に対して、$t(n)$ をそれぞれ $O(f(n))$、$\Omega(f(n))$、$\Theta(f(n))$ と表すことで概数として見積もります。また、$\Theta(f(n))$ ではない $O(f(n))$ や $\Omega(f(n))$ については、それぞれ $o(f(n))$、$\omega(f(n))$ で表します。

小学校で習う足し算の筆算は $\Theta(n)$ 時間アルゴリズム（線形時間アルゴリズム）であり、掛け算の筆算は $\Theta(n^2)$ 時間アルゴリズム（$2$ 乗時間アルゴリズム）です。このことを確認するために、$n = 5$ の場合の具体例として$42588 + 50343$ と $42588 \times 50343$ の筆算を見てみましょう。

上に示した具体例のように足し算の筆算では、赤で示した $\Theta(n)$ 個の各数字を右から左へと順に求めていきます。この各数字は $n = 5$ であることと無関係に $\Theta(1)$ 時間（定数時間）で求まります。したがって、足し算の筆算を用いた場合に $\Theta(n)$ 時間で和が求まることが確認できます。

掛け算の筆算の場合はどうでしょう。足し算の筆算と同様に詳細な解析することで、$\Theta(n^2)$ 個存在する青で示した各数字は $n$ に無関係に $\Theta(1)$ 時間で求まることが解ります。一方、赤で示した各数字は同じ列に位置する青で示した数字の個数が $k$ である場合に $\Theta(k)$ 時間で求まるため、赤で示した数字は $\Theta(n^2)$ 時間ですべて求めることができます。以上より、掛け算の筆算を用いた場合に $\Theta(n^2)$ 時間で積が求まることが確認できます。

上で確認したように、足し算の筆算は $\Theta(n)$ 時間アルゴリズム、掛け算の筆算は $\Theta(n^2)$ 時間アルゴリズムであることが判明したため、どちらがどのくらい速く問題を解くことができるか比較できるようになりました。足し算の筆算が掛け算の筆算と比較して $\Theta(n)$ 倍だけ速く問題を解くことができることが示されたことになります。

しかし、これまで見てきたのは小学校で習う筆算という特定のアルゴリズムについての比較であって、足し算と掛け算のどちらがどれだけ解くことの難しい計算問題か？という疑問に答えたことにはなりません。足し算、掛け算のどちらであっても、答えを求めるために $\Omega(n)$ 時間を要することは明らかです。なぜなら、答えに現れる数字の個数が $\Omega(n)$ だからです。したがって、$o(n)$ 時間アルゴリズムは存在しません。このことは、足し算においては、筆算のような $O(n)$ 時間アルゴリズムが最速であることを意味します。掛け算についてはどうでしょう。もしも $O(n)$ 時間アルゴリスムが存在するならば、引き分け、つまり足し算と掛け算は（計算時間における定数倍の違いを無視すると）同程度に解くことが容易な問題ということになりますが、この文章を書いた時点において、掛け算の $O(n)$ 時間アルゴリズムが存在するか否か（言い換えると、掛け算の答えを求めるために $\omega(n)$ 時間を必要とするか否か）については知られていません。つまり、引き分けである可能性は未だ残されているということになります。

ちなみに、小学校で教わった筆算よりも速く掛け算をすることのできるアルゴリズム（$o(n^2)$ 時間アルゴリズム）は存在します。長い間そのようなアルゴリズムは知られていなかったものの、1960年に $O(n^{1.585})$ 時間アルゴリズムが発明され、2007年にはほぼ $O(n \log n)$ 時間を達成するアルゴリズムが提案されています。これらのアルゴリズムは、桁数 $n$ が十分に大きい場合に筆算よりも速く答えを求めることに役立ちます（ただし、$O(f(n))$ 表示で隠されている比例係数が大きいため、桁数が小さい場合には筆算を用いたほうがより速く答えを求められます）。いつの日にか $O(n)$ 時間アルゴリズムが発見される可能性がないわけではありませんが、$\Omega(n \log n)$ 時間が必要であるとも予想されており、そのギャップを埋めることを目指して研究が続けられています。

ここまで、身近な計算問題である足し算や掛け算を例に、理論計算機科学においてどのような観点からの議論がなされているか紹介しましたが、議論の対象となる計算問題は多岐にわたります。当研究室では、文字列を扱う計算問題を対象に、計算時間や計算過程で使用する記憶領域の節約に関して効率のよいアルゴリズムを設計することを目指しています。

トップに戻る 

$2$ 本の文字列の（シークエンス）アラインメントは、それぞれの文字列の対応する位置に現れる文字が似たもの同士となるように、適切な位置にギャップ記号（－）を挿入したものです。下図は、タンパク質をコードするアミノ酸配列（の一部）同士のアラインメントの具体例です。挿入されたギャップ記号は赤い文字として表示されています。上手くアラインメントを求めることができれば、一方の文字列のどの部分が他方の文字列のどの部分に対応しているか推測することに利用できるかもしれません。あらかじめ文字同士の各ペアについて類似度を得点として定めておき（だたし、連続するギャップ記号の区間については長さに応じた特別な得点が設定されることもあります）、それぞれの文字列において対応する位置に現れる文字同士の類似度の合計が最大になるアラインメントを求める問題を、アラインメント問題といいます。

アラインメント問題の中で各文字ペアの得点設定が最も単純なものは、最長共通部分列問題とよばれる理論計算機科学における古典的な問題の一つと見なすことができます。文字列に現れる各文字を任意に削除することで結果として得られる文字列を、元の文字列の部分列といいます。最長共通部分列問題は、$2$ 本の文字列に共通の文字列で長さが最大のものを、どれでもいいから一つ求める問題です。下に示すように、最長共通部分列問題は、ペアとなる文字同士が一致する場合は $1$、一致しない場合は $0$ を類似度と設定した場合のアラインメント問題と見なすことができます（この具体例では文字列 $\mathtt{ATGCATT}$、$\mathtt{ATCTGATC}$ の最長共通部分列として $\mathtt{ATCAT}$ の場合を図示しています）。

最長共通部分列問題を解くためのアルゴリズムは、動的計画法とよばれる手法に基づく1970年頃から知られているものが有名です。このアルゴリズムの概要を、グラフとよばれるネットワーク構造を表すのに便利な概念を用いて見てみましょう。グラフは、いくつかの頂点とよばれる点と、いくつかの辺とよばれる頂点のペアを結ぶリンクからなります。動的計画法に基づいて最長共通部分列を求めるアルゴリズムで用いるグラフは、頂点が格子状に並び、横向きの辺、縦向きの辺のほかに、いくつかの斜め向きの辺をもちます。下の図は、具体例として上に示した最長共通部分列を求める際に用いられる格子グラフです。数字の記された四角形が各頂点を表します。縦向き辺の各行は上から順に $1$ 本目の文字列の先頭からの各文字に対応し、横向き辺の各列は左から順に $2$ 本目の文字列の先頭からの各文字に対応します。対応する文字が同じである行と列の交差する位置にのみ斜め向き辺があります。左上端の頂点から右下端の頂点への各経路（辺をたどる道筋）は、$2$ 本の文字列のそれぞれ異なるアラインメントを表します。経路の横向き辺、縦向き辺はそれぞれ $1$ 本目の文字列、$2$ 本目の文字列へのギャップ記号の挿入位置を表し、斜め向き辺はアラインメントにおいて文字同士が一致する位置を表します。したがって、通過する斜め向き辺の個数が最大の経路（言い換えると、最短経路、つまり通過する辺の個数が最小の経路）が最長共通部分列に対応するアラインメントを表します。赤で示した経路は、上の図で提示した最長共通部分列の具体例に対応するアラインメントを表しています。各頂点の値は、左上端の頂点からの経路が通る辺の個数の最小数を表します。この値は、辺で結ばれた左上、上、左に位置する高々 $3$ 個の各頂点における値の最小値に $1$ を加えたものとして求まります。最長共通部分列を表す経路は、右下端の頂点から順に、辺で結ばれていて値が $1$ だけ小さい任意の頂点へと逆向きにたどる（必ず左上端に到達します）ことで得られます。

$2$ 本の文字列の長さがどちらも $O(n)$ であるとすると、上に説明した格子グラフの頂点数は $O(n^2)$ です。左上端から右下端へと順に各頂点の値は $O(1)$ 時間で求まるため、すべての頂点を値を求めるのに $O(n^2)$ 時間で十分です。この作業の後には、最短経路を右下端から左上端へと逆向きに $O(n)$ 時間でたどれます。したがって、このアルゴリズムは、長さ $O(n)$ の $2$ 本の文字列に対して $O(n^2)$ 時間で最長共通部分列を求めることができるということになります。2015年になって、任意に小さな正の定数 $\epsilon$ に対して、最長共通部分列問題を $O(n^{2 - \epsilon})$ 時間で解くことが困難であると示唆する理論的な証拠が示されました。このことは、動的計画法に基づくこの $O(n^2)$ 時間アルゴリズムがほぼ最速であると扱うに値することを意味します（なお、$o(n^2)$ 時間アルゴリズムとしては、1980年に提案された $O(n^2/\log n)$ 時間アルゴリズムが知られています）。

最長共通部分列問題がもつ本質的な性質は、上の議論でほぼ解明しつくされたと言えるでしょうか。必ずしもそうとは言い切れません。関連する別の問題を解く際に、最長共通部分列問題がもつ未だ注目されていない何らかの性質が役に立つかもしれないからです。

例えば、長さ $O(n)$ の $2$ 本の文字列が初めに指定され、その後にオンライン的な環境のもとで長さ $O(n)$ の任意の部分文字列（連続する区間に現れる文字のみからなる部分列）が次々に指定され、その都度、指定された部分文字列同士の最長共通部分列を求めなければならない状況を想定してみましょう。上に紹介した動的計画法に基づく $2$ 乗時間アルゴリズムを用いれば、毎回 $O(n^2)$ 時間で指定された部分文字列同士の最長共通部分列を求めることができます。しかし、毎回 $O(n^2)$ 時間をかける必要は本当にあるのでしょうか。より詳しく言い換えるならば、以前に別の部分文字列同士の最長共通部分列を求めたならば、その際に得られた計算の途中結果を上手く再利用することで、$o(n^2)$ 時間で今回指定された部分文字列同士の最長共通部分列が求まるのではないでしょうか。このことを突き詰めると、$2$ 本の文字列に対してあらかじめ様々な部分文字列同士の最長共通部分列を求める際に共通に利用することのできる何らかのデータを作成しておくことで、部分文字列が指定された際に上手く用いることで $o(n^2)$ 時間で最長共通部分列を求めることが可能になるのではないか？という発想に至ります。あらかじめ作成したそのようなデータを集めたものをデータ構造といい、これを作成するのに要する時間を前処理時間といいます。また、データ構造を用いて指定された部分文字列同士の最長共通部分列を求めるのに要する時間をクエリ時間といいます。

一般に、データ構造に関する前処理時間とクエリ時間の間には、一方を短くすると他方が長くなるというトレードオフの関係があります。あまりに極端で無意味な方法ですが、$O(n^6)$ 時間の前処理として $O(n^4)$ 通り存在するすべての部分文字列同士に対してあらかじめ動的計画法に基づくアルゴリズムでそれぞれ最長共通部分列を求めておくことで、各クエリに対して直ちに応えることができるようになります。ただし、直ちにと言っても最長共通部分列そのものの長さは $O(n)$ なので、クエリ時間も $O(n)$ となります。一方、データ構造を一切用意しないでクエリのたびに動的計画法に基づくアルゴリズムを用いる場合は、前処理時間は $O(1)$ となり、クエリ時間は $O(n^2)$ 時間となります。

この枠組みで考えた場合に、部分文字列同士の最長共通部分列を求めるためのデータ構造として最も望ましい前処理時間とクエリ時間の組み合わせはどのようなものになるでしょう。前処理時間とクエリ時間の合計を $O(n^{2 - \epsilon})$ とすることは（先に述べたように理論的な証拠の存在により）事実上不可能であることから、$O(n^2)$ を望ましい前処理時間と扱うことには妥当性があると言えるかもしれません。また、上で述べたように、クエリ時間については $O(n)$ が最良です。だとしたら、前処理時間が $O(n^2)$ でクエリ時間が $O(n)$ のデータ構造は設計できるでしょうか。別の言い方をするならば、$2$ 本の文字列全体同士の最長共通部分列を求めるのに要するのとほぼ同じ時間の前処理をしさえすれば、任意に指定される部分文字列同士の最長共通部分列を直ちに（つまり線形時間で）求めることができるようになるでしょうか。

できるようになります！

当研究室では、前処理時間が $O(n^2)$ でクエリ時間が $O(n)$ のデータ構造を具体的に設計することによって、このことを初めて証明することに成功しました。

トップに戻る 

$2$ 本の文字列の極大共通部分列は、それぞれの文字列に現れる共通の部分列で、どの位置にどの文字を追加（挿入）したとしても、もはや $2$ 本の文字列に共通に現れる部分列とはならないものを言います。最長共通部分列は必ず極大共通部分列でもあります。一方、極大共通部分列は必ずしも最長共通部分列ではありません。例えば、$2$ 本の文字列 $\mathtt{ATGCATT}$、$\mathtt{ATCTGATC}$ において $\mathtt{ATGC}$ は極大共通部分列ですが、最長共通部分列ではありません。なぜなら、より長い共通の部分列として $\mathtt{ATCAT}$ や $\mathtt{ATCTT}$、$\mathtt{ATGAT}$ などが存在するからです。

共通部分列の極大性という概念は、何らかの条件を満たす最長共通部分列を求める問題において意義が生じる可能性があります。例えば、制限最長共通部分列問題は、$2$ 本の文字列の他に、それらに共通に現れる部分列が制限パターンとして与えられ、この制限パターンが部分列として現れないような長さが最大の共通部分列を求める問題です。制限最長共通部分列を求めることの意図として、制限パターンを敢えて対応付けなかった場合に $2$ 本の文字列においてどのような対応関係が見出せるか知りたいという状況が考えられるかもしれません。しかし、制限パターンが共通部分列として現れない長さが最大の共通部分列という条件のみで探すと、制限パターンが共通部分列として現れる共通部分列から敢えて文字を一つ（あるいは数個）のみ削除することで得られただけのものが見出される可能性があります。下に示した図はその解りやすい一例で、制限パターンとして $\mathsf{bbcccbbb}$ が設定された場合に、この $\mathsf{bbcccbbb}$ が共通部分列として現れる長さ $11$ の共通部分列 $\mathsf{bbbcbccbbbb}$ から、それに現れる文字 $\mathsf{c}$ を任意に一つだけ削除することで得られる長さ $10$ の共通部分列 $\mathsf{bbbbccbbbb}$、$\mathsf{bbbcbcbbbb}$ のどちらかが見つかることになります。しかし、どちらが得られたとしても意図に反するものと言えるでしょう。

このような状況を回避するには、探すべき共通部分列に極大という条件を加える必要があります。この条件のもとでは、下に示すような長さ $9$ の $\mathsf{aaaaaaaaa}$ が、長さが最大の極大共通部分列として見出されることになります。

ところで、長さが $O(n)$ の $2$ 本の文字列に対して極大共通部分列を（どれでもいいから一つ）見つけるには、どれだけの時間がかかるでしょう。最長共通部分列は極大共通部分列の特別な一例なので、動的計画法に基づくアルゴリズムを用いることで $O(n^2)$ 時間あれば十分です。しかし、この方針をとる限り、極大共通部分列を $O(n^{2 - \epsilon})$ 時間で求めることは実質的に不可能（このことを示唆する理論的な証拠が存在するため）ということになります。別の方針をとることで、もっと速く求めることは可能でしょうか。別の言葉で表現するならば、極大共通部分列を見つけ出すことと、最長共通部分列を見つけ出すことは、本質的にどのくらい困難さが異なるのでしょう。

当研究室では、この問に対する回答として、極大共通部分列が理論上最速（定数倍の違いは無視する）である線形時間で求まることを、$O(n)$ 時間アルゴリズムを設計することで示しました。ただし、この計算時間は文字列に現れる文字の種類が文字列の長さ $O(n)$ に無関係な定数である場合（例えば、DNAの塩基配列における $4$ 種類やアミノ酸配列における $20$ 種類のような場合）についてであって、$O(n)$ 種類の文字が現れる場合は $O(n \log n)$ 時間がかかります。更に、関連する計算問題として、極大か否かが不明な共通部分列が与えられたときに、これが極大か否かの判定を線形時間でできることも、同様に $O(n)$ 時間アルゴリズムを設計することで証明しました。こちらについては、たとえ文字列に $O(n)$ 種類の文字が現れる場合であっても線形時間で判定できます。

（これらの成果を発表した「組合せ論的パターン照合(Combinatorial Pattern Matching)」の第29回年次国際シンポジウムにてベスト論文賞(Apostolico Award)を授与されました。）

トップに戻る 

各要素が数値である数値列において合計値が最大であるような区間を求める問題を、最大和断片問題と言います。数値列の各数値がその位置における何らかの重要度を表す値として設定されている場合、この問題は数値列における重要な領域を最大和断片として特定する問題であると見なすことができます。例えば、下の図のような異なる生物種の相同なタンパク質をコードしているアミノ酸配列同士のアラインメントにおいて、各位置のアミノ酸同士の類似度からなる数値列における最大和断片を求めることは、タンパク質を機能させるために欠かすことのできない重要な領域を推定することに役立つかもしれません。なぜなら、得られた最大和断片の位置に存在する各アミノ酸について、タンパク質の機能を保持するのに重要であるからこそ進化の過程において著しい変異を受け入れることなく維持されてきたと想定できるからです。

長さが $O(n)$ の数値列に対して、最大和断片を求めるのにどのくらいの時間がかかるでしょう。速く求めるための工夫をまったくしないならば、$O(n^2)$ 通りの区間が存在して、それぞれの区間で合計値を求めるために $O(n)$ 時間がかかるので、全体として$O(n^3)$ 時間かかるということになります。速く求めるための工夫をした場合はどうでしょう。理論上最速（ただし、定数倍の違いは無視）である $O(n)$ 時間アルゴリズムが1984年に提案されています。さらに興味深いことに、2004年には、数値列の任意に指定された区間における最大和断片を求めるための前処理時間 $O(n)$、クエリ時間 $O(1)$ のデータ構造が提案されました。数値列の区間は $O(n^2)$ 通り存在するので、$O(n)$ 時間の前処理で $O(n^2)$ 通りの各区間に対する最大和断片がすべて求まることを意味します。ただし、求まっているだけで、すべてを明示的に取り出すためには $O(n^2)$ 時間かかります。任意の順に一つの区間あたり最大和断片を（数値列の長さ $O(n)$ に無関係な）定数時間で取り出せることが注目すべき利点です。

上で紹介したように、数値列の最大和断片は理論上改良の余地のない速さで見つけ出すことができることが知られています。しかし、見つけ出される断片が数値列上のどの位置になるかについては定かではありません。一方、もしも指定した位置を含むというという条件のもとで重要な連続領域を知りたい場合には、その位置を含む合計値が最大の区間を見つけたとしても、意図するものと異なっているかもしれません。例えば、下に図示した数値列において▲印の位置を含む重要な連続領域を知りたいとしましょう。この位置を含む合計値が最大の区間は、数値列の下側に示されている合計値 $10$ の区間となります。ところが、この区間の内部について構造をよく観察すると、全体の合計値 $10$ を超える合計値をもつ区間が存在していることに気がつきます。最大の合計値をもつそのような区間は、数値列の上側に示している $3$ 個の区間のうち左側と右側のもので、どちらの区間も合計値は $11$ です。そして、これらの区間はどちらも指定された位置を含みません。つまり、指定された位置を含む合計値 $10$ の区間の重要性の本質は、指定された位置を含まない合計値 $11$ の区間の重要性にあるということになります。では、指定された位置を含むという条件のもとで、このような不自然なことが起こらないような重要な区間として、どのようなものを見つけ出せばよいのでしょう。

数値列上のある区間が、その区間全体を自身の最大和断片としてもつとき、その区間を局所最大和断片と呼ぶことにしましょう。したがって、上の例に示した指定された位置を含む合計値が $10$ の区間は、合計値 $11$ の区間を内部にもつという意味で、局所最大和断片ではありません。逆に考えると、局所最大和断片ではない区間は、必ず自身における合計値を超える合計値をもつ区間を内包し、この内部区間がもつ合計値の大きさをそれ以外の部分が相殺しているという意味で、求めるべき重要な区間として望ましくない構造をもっていると言えるでしょう。したがって、含むべき位置を指定された場合、求めるべき重要な区間としては、指定された位置を含む局所最大和断片で極大なもの（つまり、範囲を更に広げると局所最大和断片でなくなるか合計値が小さくなるもの）と定義するのが妥当と言えそうです。上の具体例においては、数値列の上側に示した $3$ 個の区間のうち合計値が $6$ である中央のものが、▲印の位置を含む極大な局所最大和断片となります。なお、含むべき位置が特に指定されない通常の最大和断片として見つかる区間も、必ず極大な局所最大和断片の条件を満たします。この意味で、指定された位置を含む極大局所最大和断片を求める問題は、最大和断片問題の自然な拡張であると言えます。

当研究室では、指定された位置を含む極大局所最大和断片を求める問題についても、拡張前のオリジナルな最大和断片問題の場合と同様に、効率よく解くことができることを示しました。具体的には、長さが $O(n)$ の数値列に対して、$O(n)$ 時間の前処理をすることで、数値列上の区間と区間内の位置が指定されるたびに、指定された区間における指定された位置を含む極大局所最大和断片を $O(1)$ 時間で求めることができることを、具体的なデータ構造を設計することで証明しました。

トップに戻る