(57)【要約】【課題】互いにスプライシングバリアントの関係にある配列を含む多数の生体高分子配列データから，個々のエクソンに相当する部分配列を，効率よく抽出する。【解決手段】エクソン配列が満たすべき条件を用いて，エクソン配列のモデルを構築し，そのモデルに沿ってエクソン配列を定義する。そして，モデルで定義されたエクソン配列を，入力として与えられた生体高分子配列から抽出する。本発明の方法は，与えられた生体高分子配列に基づきｓｕｆｆｉｘ  ｔｒｅｅを構築し，配列中の文字数や配列数に依存しない回数の，ｓｕｆｆｉｘ  ｔｒｅｅ上の深さ優先探査および配列中の各文字の位置に関する処理によって，入力として与えられた生体高分子配列の長さの総和に対し，線形時間で抽出処理を完了できる。【選択図】  図１
2004152023.tif 000002
【特許請求の範囲】
【請求項１】
複数の文字列が入力として与えられたときに，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右または左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列を，ＭＵＭと呼ぶとき，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，
長さが指定された整数ｕ以上であり，
与えられた各文字列には高々１度しか現れず，
該部分文字列が，該部分文字列を完全に含むＭＵＭ以外のどのＭＵＭとも，どの与えられた文字列上でも文字を共有することがなく，
上記４つの条件のみを満足するほかの部分文字列の一部となっていない部分文字列を抽出することを特徴とする文字列解析方法。
【請求項２】
請求項１記載の文字列解析方法において，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列である，右ＭＵＭと呼ぶ部分文字列を抽出する工程と，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，
該部分文字列の左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる文字列である，左ＭＵＭと呼ぶ文字列を抽出する工程または，前記ＭＵＭと呼ばれる部分文字列を抽出する工程と，
ＭＵＭであるか，またはある与えられた文字列上で，あるＭＵＭの次の文字から始まる右ＭＵＭであって，真のｐｒｅｆｉｘとして右ＭＵＭである文字列を含まない文字列を抽出する工程とを有することを特徴とする文字列解析方法。
【請求項３】
複数の文字列が入力として与えられたときに，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右または左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列を抽出する方法であって，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列を抽出する工程を有することを特徴とする文字列解析方法。
【請求項４】
請求項３記載の文字列解析方法において，与えられた文字列を格納したｓｕｆｆｉｘｔｒｅｅを利用し，ｓｕｆｆｉｘ  ｔｒｅｅ内のノードについて，該ノードへのポインタとなっているｓｕｆｆｉｘ  ｌｉｎｋの数を数えることを特徴とする文字列解析方法。
【請求項５】
複数の文字列が与えられたときに，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列である，右ＭＵＭと呼ぶ部分文字列を抽出する工程と，与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが本発明の方法の利用者が指定する整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列であるものを抽出する工程とを有し，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右または左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となる部分文字列をＭＵＭと呼ぶとき，
ＭＵＭか，または，ある与えられた文字列上であるＭＵＭの次の文字から始まる右ＭＵＭであって，右ＭＵＭである文字列を真のｐｒｅｆｉｘとして含まない部分文字列を抽出することを特徴とする文字列解析方法。
【請求項６】
複数の文字列が与えられたときに，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となるとき該部分文字列を右ＭＵＭと呼び，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右または左に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となるとき該部分文字列をＭＵＭと呼ぶとき，
ＭＵＭか，または，ある与えられた文字列上であるＭＵＭの次の文字から始まる右ＭＵＭであって，右ＭＵＭである文字列を真のｐｒｅｆｉｘとして含まない部分文字列を抽出する工程を有する文字列解析方法であって，
与えられた文字列におけるＭＵＭの位置を計算するために，右ＭＵＭを真のｓｕｆｆｉｘとしない右ＭＵＭの位置を計算することを特徴とする文字列解析方法。
【請求項７】
請求項１記載の文字列解析方法において，
与えられた文字列のうち少なくとも１つの文字列の部分文字列であって，長さが指定された整数ｕ以上であり，与えられた各文字列には高々１度しか現れず，該部分文字列の右に一文字追加して得られる新しい文字列を含む与えられた文字列の集合が，文字を追加する前の該部分文字列を含む与えられた文字列の集合と異なる集合となるときに該部分文字列を右ＭＵＭと呼ぶとき，
前記ＭＵＭであるかまたは，ある与えられた文字列上であるＭＵＭの次の文字から始まる右ＭＵＭであって，真のｐｒｅｆｉｘとして右ＭＵＭである文字列を含まない部分文字列のｐｒｅｆｉｘだけを抽出すべき部分文字列の候補とすることを特徴とする文字列解析方法。
【請求項８】
請求項１〜７のいずれか１項記載の文字列解析方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，複数の文字列，特に生体高分子配列に共通に存在する部分文字列を抽出するための文字列解析方法に関し，生体高分子配列のスプライシングパターン解析方法に適用して好適な方法に関する。
【０００２】
【従来の技術】
国際共同プロジェクト及び米国ベンチャー企業により，２０００年６月にヒトゲノムの文字配列決定の完了が宣言された。ゲノム配列の解析が進む一方で，発現している遺伝子について調べるために，ｍＲＮＡの解析が行なわれている。ｍＲＮＡは，遺伝子が発現する際，ゲノムＤＮＡから生成されるＲＮＡ分子で，遺伝子の機能発現の過程で不可欠な物質である。ｍＲＮＡ分子は分解しやすいため，逆転写によりｍＲＮＡよりも安定な物質であるｃＤＮＡに転換し解析されることが多い。ｃＤＮＡのシングルパス配列決定で得られた配列は，ＥＳＴと呼ばれる。ＥＳＴには様々な利用価値があるが，そのひとつが，遺伝子がどのようなエクソンにより構成されているかを明らかにすることである。
【０００３】
図２は，ゲノム配列２０１上の遺伝子２０２と，ｍＲＮＡ  ２０７との関係を説明する図である。遺伝子が発現する際，ゲノム配列上の該遺伝子２０２が転写されｍＲＮＡ前駆体２０３が作られる。矢印２０４で象徴的に示すスプライシングと呼ばれる過程を経てｍＲＮＡ前駆体２０３のイントロン２０５が除去されてエクソン２０６のみから成るｍＲＮＡ  ２０７が構成される。生体内では，このｍＲＮＡ  ２０７に基づき，タンパク質が合成される。
【０００４】
スプライシングの過程で，同一エクソンが常に同じように残されるとは限らない。図２に示したように，同一遺伝子由来のｍＲＮＡであっても，あるｍＲＮＡ２０７で残されたエクソン２０８が，別のｍＲＮＡ  ２０９では除去されることがあり，逆に，あるｍＲＮＡ  ２０７で除去されたエクソン２１０が別のｍＲＮＡ２０９では残される場合もある。ｍＲＮＡ  ２０７とｍＲＮＡ  ２０９のように，同一遺伝子由来のｍＲＮＡで，スプライシングを受ける領域が異なるものを，互いにスプライシングバリアントであると言う。ヒトの場合，生体内のタンパク質は１０万種類以上存在するといわれる一方，遺伝子数は３万〜４万のみといわれており，スプライシングバリアントがこの差を埋めていると考えられている。こうしたスプライシングバリアントの解析は，遺伝子の機能発現を解析するにあたり不可避であり，生命現象の解明や，ゲノム創薬のために不可欠である。
【０００５】
同一遺伝子に由来するあらゆるスプライシングバリアントの配列を網羅する十分な量のＥＳＴを収集し解析することは，ｍＲＮＡのエクソン構造を明らかにする有力な手段となる。ＥＳＴなど転写産物由来の配列のみに基づきスプライシングバリアントの解析を行なうためには，複数の配列から個々のエクソンに相当する部分配列をいかにして抽出するかが課題となる。ところが，与えられた配列データのあらゆる部分配列を網羅的に列挙し，エクソン配列か否かを調べるアプローチは，各入力配列に対してその配列長の２乗のオーダーの部分配列が存在し，複数の入力配列間でそれらの比較を行なうと，与えられた配列の文字の総数をさらに乗じたオーダーの計算時間が必要となる。従って，処理すべきデータ量が増加すると，処理に必要な時間が急激に増加し，実用的なシステムを作ることは困難である。その一方で，米国公共機関のデータベースに蓄積されているＥＳＴのデータ量は，配列決定技術の進歩に伴い急速に増大しつつあり，ヒトだけで４５０万配列を超えている。こうした膨大な配列データを解析するために，高速な計算方法が必要である。
【０００６】
Ａｌｔｓｃｈｕｌ，  Ｓ．Ｆ．  ｅｔ  ａｌ．，  Ｎｕｃｌｅｉｃ  Ａｃｉｄ  Ｒｅｓｅａｒｃｈ，  ２５：３３８９−３４０２，  １９９７のホモロジー検索の方法はＥＳＴの解析にも使われている。もし，ＥＳＴ以外にゲノム配列も利用可能ならば，ゲノム配列の部分文字列で，  ＥＳＴにも存在する部分文字列がエクソンであると，高い精度で予想することができる。ただし，対応するゲノム配列が無いＥＳＴを解析する場合に，ホモロジー検索の方法を使って転写産物由来配列間の相互の関係を調べようとすれば，最悪の場合配列数の２乗のオーダーの計算が必要となり，配列数が増加するとエクソン構造を予想することは容易ではない。しかも，Ａｌｔｓｃｈｕｌらの方法ではショートエクソンを捕らえられない場合がある。
【０００７】
複数の配列に共通する部分配列の抽出を効率よく行なう手法として，Ｄｅｌｃｈｅｒ  ｅｔ  ａｌ．，  Ｎｕｃｌｅｉｃ  Ａｃｉｄｓ  Ｒｅｓｅａｒｃｈ，  １９９９，  ２７（１１）：２３６９−２３７６の方法が知られている。Ｄｅｌｃｈｅｒらの手法は，主に２つの近縁種のゲノムを比較することを目的としている。この手法では，まず次の（Ｄ１）−（Ｄ４）の条件を満足するＭＵＭ（Ｍａｘｉｍａｌ  Ｕｎｉｑｕｅ  Ｍａｔｃｈ）と呼ばれる部分配列を探索する。
（Ｄ１）  ＭＵＭは，長さがユーザに指定されたパラメータ以上の配列長をもつ部分配列である。
（Ｄ２）  ＭＵＭは，２つの配列の，共通の部分配列である。
（Ｄ３）  ＭＵＭは，２つのそれぞれの配列内に，１つしか含まれない。
（Ｄ４）  ＭＵＭは，別のＭＵＭの部分配列にならない。すなわち，前記（Ｄ１）−（Ｄ３）を満足する配列を，可能な限り延長して得られた配列のみがＭＵＭである。
【０００８】
Ｄｅｌｃｈｅｒらの方法をＥＳＴに適用し，ＭＵＭとしてアラインされる部分や大きな挿入や欠失が入る位置を同定すれば，ＭＵＭはエクソン配列に対応し，大きな挿入や欠失は，選択的なエクソンに対応すると考えることができ，エクソン構造を同定するためのツールとして使うことができる。しかし，Ｄｅｌｃｈｅｒらの方法は２配列のみを対象としており，配列数が３つ以上になったときには適用することができない。
【０００９】
３つ以上の文字列から共通する部分配列を抽出する方法としては，文字列処理に広く応用されているデータ構造であるｓｕｆｆｉｘ  ｔｒｅｅを活用したＧｕｓｆｉｅｌｄ，  Ｄ．，  Ａｌｇｏｒｉｔｈｍｓ  ｏｎ  Ｓｔｒｉｎｇｓ，  Ｔｒｅｅｓ，  ａｎｄ  Ｓｅｑｕｅｎｃｅｓ：  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｂｉｏｌｏｇｙ．  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  Ｎｅｗ  Ｙｏｒｋ  のｃｈａｐｔｅｒ  ９に記載の，ｌｏｎｇｅｓｔ  ｃｏｍｍｏｎ  ｓｕｂｓｔｒｉｎｇ  ｐｒｏｂｌｅｍに対する線形時間解法が知られている。この方法を用いると，任意の数の文字列について，指定された数以上の文字列に共通の部分文字列の中でもっとも長い部分文字列を，文字総数の線形時間で抽出することができる。ただし，複数のエクソンを連結した文字列や，互いに重なっている文字列を抽出してしまう場合があり，この方法で抽出した配列がそのままエクソンに相当する配列と考えることはできない。
【００１０】
【発明が解決しようとする課題】
本発明は，転写産物由来の複数の配列に基づき，これらの配列に含まれるエクソン配列を抽出することを目的としている。
【００１１】
転写産物由来の配列だけに基づき，個々のエクソンの配列を完全に同定できれば理想だが，現実にはそれが常に可能なわけではない。ある遺伝子が４つのエクソンＡ，Ｂ，Ｃ，Ｄを持ち，それらのエクソンはこの順序でゲノム上に並んでいるとする。仮に，ＢとＣがスプライシングの過程を経て常に同時にｍＲＮＡに現れるならば，ＥＳＴだけを見ている限り，Ｂ，Ｃという２つの別のエクソンがあることや，ＥＳＴ上のどこにＢ，Ｃの境界があるかを知ることは不可能である。そこで本発明では，ゲノム上の隣り合うエクソンで常に共存するものは，同一のエクソンとみなす。このほか，エクソンＢが直後にＣかＤを必ず伴うとし，ＣとＤには必ずＢが先行する場合を考える。ＣとＤの先頭の配列が一致するならば，Ｂ，Ｃ，Ｄというエクソンの存在を知ることができても，どこがＢ，Ｃ，Ｄの境界なのかを知ることはできない。そこで本発明では，確実に同一のエクソンに由来すると考えられる，エクソンの部分配列を抽出する。また，本発明では，１つの遺伝子には同一配列のエクソンは存在しないと仮定し，１配列に高々１回しか現れない部分配列のみを処理対象とする。さらに，例えば数文字程度の，長さが極端に短い部分配列は入力配列上のいたるところに現れるが，それらはエクソン配列と見なすべきでなく，エクソンはある程度以上長い部分配列であるべきである。本発明では，エクソン配列に関する上記の性質を踏まえ，エクソン配列のモデルであるＵＥＢ（Ｕｎｉｑｕｅ  Ｅｘｏｎ  Ｂｌｏｃｋ）（図３の文字列３０５参照）を定義し，ＵＥＢを抽出することを目指す。
【００１２】
ところで，次の条件を満たす文字列ｍは，複数のエクソン配列を連結した文字列になっている可能性がある。
（Ｍ１）  １つ以上の文字列の部分文字列である。
（Ｍ２）  長さｕ以上。ただし，ｕとは最も短いエクソンの長さで，パラメータとして与えられる整数である。
（Ｍ３）  各入力文字列に，高々１回しか出現しない。
（Ｍ４）  ある文字列ｓが出現する入力文字列の集合をＰ（ｓ）とする。このとき，任意の文字ａに対してＰ（ｍ）≠Ｐ（ｍａ）である。ここに，ｍａは文字列ｍの末尾に文字ａを付加した文字列である。
（Ｍ５）  任意の文字ａに対してＰ（ｍ）≠Ｐ（ａｍ）である。ここに，ａｍは文字列ｍの先頭に文字ａを付加した文字列である。
【００１３】
なお，（Ｍ１）−（Ｍ５）を満たす文字列は，Ｄｅｌｃｈｅｒらの方法におけるＭＵＭの概念を，２配列以外の場合でも適用可能なように拡張したものである。本明細書ではこれ以降，（Ｍ１）−（Ｍ５）を満たす文字列をＭＵＭ（図３の文字列３０３参照）と呼ぶ。
【００１４】
ＵＥＢ  ３０５は，ＭＵＭ  ３０３を部分文字列として完全に含んでいたり，重なっていたりしない文字列であるべきである。ＵＥＢ  ３０５を正確に定義するために，「文字列が重なる」とはどういうことか，正確に定義する必要がある。本明細書では，図１５に示したように，次の４つの条件を満足する文字列ｔ，ｔ’，ｔ’’が存在するときに，かつそのときに限り，「文字列ｓ，ｓ’が重なる」という。
（１）  ｔ，ｔ’，ｔ’’は，長さが１以上の文字列である。
（２）  ｓ＝ｔｔ’，すなわち，ｓはｔとｔ’を連結した文字列である。
（３）  ｓ’＝ｔ’ｔ’’，すなわち，ｓ’はｔ’とｔ’’を連結した文字列である。
（４）  ある入力文字列が，ｔｔ’ｔ’’を部分文字列として含む。
【００１５】
なお，（１）−（４）が満足されるとき，「ｓはｓ’と右で重なる」，「ｓ’はｓと左で重なる」という。これらの概念を用いて，ＵＥＢを次の条件を満たす文字列と定義する。
（Ａ１）  少なくとも１つの入力文字列の部分文字列。
（Ａ２）  長さｕ以上。
（Ａ３）  各入力文字列に，高々１回しか出現しない。
（Ａ４）  ＭＵＭと重ならない。
（Ａ５）  ＭＵＭを真の部分文字列としない。なお，ある文字列の真の部分文字列とは，その文字列自身を除く部分文字列のことである。
（Ａ６）  （Ａ１）−（Ａ５）を満たす文字列の，真の部分文字列にならない。
巨大なデータを効率よく処理するためには，処理時間を入力文字列の文字数の総数に関し線形時間に抑えることが望ましい。
【００１６】
以上を踏まえ，本発明の課題は，複数の生体高分子配列に相当する文字列が与えられたときに，（Ａ１）−（Ａ６）を満足する文字列すなわちＵＥＢを，与えられた入力文字列の総文字数の線形時間で抽出する方法を提供することである。
【００１７】
【課題を解決するための手段】
本発明では，入力として複数の文字列３０１が与えられたとき，後述の右ＭＵＭ  ３０２，後述の左ＭＵＭまたはＭＵＭ  ３０３，後述の右ＵＥＢ−ｈｏｌｄｅｒ  ３０４を順次抽出し，それらを利用してＵＥＢ  ３０５を抽出する。
【００１８】
なお，左ＭＵＭの抽出（ステップＳ５０３）と，ＭＵＭの抽出（ステップＳ５０４）は，どちらか片方だけを行なえばよい。ステップＳ５０３により左ＭＵＭを使う方法はわかりやすく実装の手間もそれほどではないが，計算機の主記憶を多く使用する問題がある。一方，ステップＳ５０４によりＭＵＭを抽出する方法は，実装の手間が若干かかるものの，消費する計算機の主記憶が少なく，速度も速いと予想される。
以下，本発明の特徴を述べる。
【００１９】
本発明の方法は，複数の入力文字列が与えられたときに，ＵＥＢを抽出する方法であって，入力文字列の文字数の総和に対し線形時間で処理を完了できる。
本発明の方法は，ＵＥＢを抽出するために，右ＭＵＭを抽出する工程と，ＭＵＭを抽出する工程または前述の左ＭＵＭを抽出する工程と，右ＵＥＢ−ｈｏｌｄｅｒを抽出する工程とを有し，それぞれの工程で，入力文字列を格納したｓｕｆｆｉｘ  ｔｒｅｅを用いることを特徴とする。
【００２０】
本発明の方法はまた，ＭＵＭを抽出する工程において，右ＭＵＭを抽出しその中からＭＵＭの条件を満足する部分文字列を選択し，抽出することを特徴とする。
本発明の方法はまた，ＭＵＭを抽出する工程において，ｓｕｆｆｉｘ  ｔｒｅｅ内のノードについて，そのノードを参照するｓｕｆｆｉｘ  ｌｉｎｋの数を数えることを特徴とする。
本発明の方法はまた，右ＵＥＢ−ｈｏｌｄｅｒを抽出する工程を有することを特徴とする。
【００２１】
本発明の方法はまた，右ＵＥＢ−ｈｏｌｄｅｒを抽出する工程において，入力文字列上のＭＵＭの位置を解析するために，他の右ＭＵＭを真のｓｕｆｆｉｘとしない右ＭＵＭの位置のみを計算することを特徴とする。
本発明の方法はまた，右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘのみを，ＵＥＢの候補とみなすことを特徴とする。
【００２２】
【発明の実施の形態】
以下，図面を参照して本発明の実施の形態について説明する。最初に，本明細書で使用する記号と用語及び概念を定義する。なお，本発明の方法は，塩基配列だけでなく，アミノ酸配列など他の種類の文字列に対しても適用可能である。そこで，以下では，配列を文字列と呼び，塩基を文字と呼ぶこととする。
【００２３】
はじめに，すでに公知である概念について，本明細書で用いる記号および厳密な意味を定義する。
●空文字列
長さが０の文字列。本明細書では，以下，空文字列をεと表記する。
●文字列の連結
文字列ｓ，ｔを連結した文字列をｓｔと表記する。
●Ｐｒｅｆｉｘ
ある文字列の部分文字列で，先頭がもとの文字列に一致するもの。
ある文字列ｔがｔ＝ｐｓと書けるとき，ｐはｔのｐｒｅｆｉｘである。ここで，ｓは空文字列であってもよい。すなわち，ｔはｔ自身のｐｒｅｆｉｘである。ｓ≠εのとき，ｐをｔの真のｐｒｅｆｉｘと呼ぶ。
例えば，「Ａ」，「ＡＴ」，「ＡＴＡ」，「ＡＴＡＴ」，「ＡＴＡＴＧ」は文字列「ＡＴＡＴＧ」のｐｒｅｆｉｘである。これらのうち「ＡＴＡＴＧ」以外は，真のｐｒｅｆｉｘである。
【００２４】
●Ｓｕｆｆｉｘ
ある文字列の部分文字列で，末尾がもとの文字列に一致するもの。
ある文字列ｔがｔ＝ｐｓと書けるとき，ｓはｔのｓｕｆｆｉｘである。ここで，ｐは空文字列であってもよい。すなわち，ｔはｔ自身のｓｕｆｆｉｘである。ｐ≠εのとき，ｓをｔの真のｓｕｆｆｉｘと呼ぶ。
例えば，「Ｇ」，「ＴＧ」，「ＡＴＧ」，「ＴＡＴＧ」，「ＡＴＡＴＧ」は文字列「ＡＴＡＴＧ」のｓｕｆｆｉｘである。これらのうち「ＡＴＡＴＧ」以外は，真のｓｕｆｆｉｘである。
【００２５】
●｜ｓ｜
文字列ｓの長さ。
●｜Ａ｜
集合Ａの要素数。
●⊆，⊇，⊂，⊃
本明細書では，２つの集合Ａ，Ｂについて，「Ａ⊆Ｂ」とは，Ａの全ての要素がＢの要素であることを表し，「Ａ⊇Ｂ」とはＢ⊆Ａを表す。「Ａ⊂Ｂ」とは，Ａ⊆Ｂ  かつＡ≠Ｂのことであり，「Ａ⊃Ｂ」とはＢ⊂Ａ  を表す。
【００２６】
●Ｏ（ｆ（ｎ））
ｇ（ｎ）＝Ｏ（ｆ（ｎ））  であるとは，ある定数Ｃが存在して，十分大きなｎに対しｇ（ｎ）≦Ｃｆ（ｎ）が成立することである。また，ある量が「Ｏ（ｆ（ｎ））である」とは，その量がｎのある関数ｇ（ｎ）以下であり，ｇ（ｎ）＝Ｏ（ｆ（ｎ））であることを意味する。このような表記法は，ｂｉｇ−Ｏ  ｎｏｔａｔｉｏｎと呼ばれている。
【００２７】
●Ｓｕｆｆｉｘ  ｔｒｅｅ
文字列Ｐ１，Ｐ２，…，Ｐｎのｓｕｆｆｉｘ  ｔｒｅｅ  とは，Ｐ１，…，Ｐｎに現れる全てのｓｕｆｆｉｘ  を格納したｔｒｅｅ状のデータ構造で，以下の性質をもつ。なお，２つの文字列「ＡＴＡＴＧ」，「ＴＴＡＧＴＡ」を格納したｓｕｆｆｉｘ  ｔｒｅｅ  ４０１を図４に図示した。
（Ｓ１）  ルートノード４０２を持つ有向木である。
（Ｓ２）  Ｐ１，  …，  Ｐｎ  の文字列長の総和に等しい数のリーフ４０３を持つ。それらのリーフには，文字列番号と文字列中の位置が，互いに重複しないように割り当てられる。
（Ｓ３）  それぞれのエッジ４０４には，Ｐ１，．．．，  Ｐｎのうち，どれか１つの文字列の部分文字列がラベル４０５として付加されている。さらに，リーフに直接至るエッジ以外のラベルは，空文字列４０６であってはならない。なお本明細書では，文字列ｉのｊ番目の文字で始まるｓｕｆｆｉｘに対応するリーフを，以下ではリーフ（ｉ，ｊ）と呼ぶ。また，本明細書では，文字列の先頭の文字を０番目と数える。
（Ｓ４）  任意のノード４０７を起点とするエッジに，同じ文字で始まるラベル４０５を持つエッジのペアは存在しない。
（Ｓ５）  ルートノード４０２から文字列番号ｉと文字列中の位置ｊが割り当てられたリーフ４０３へのパス上にあるエッジのラベルを，このパス上で出会う順に連結すると，文字列ｉのｊ番目の文字で始まるｓｕｆｆｉｘとなる。
（Ｓ６）  任意のノードｖを起点として伸びるエッジの数は１でない。
なお本明細書では，文字列ｉのｊ番目の文字で始まるｓｕｆｆｉｘに対応するリーフ４０３を，以下ではリーフ（ｉ，ｊ）と呼ぶ。
Ｓｕｆｆｉｘ  ｔｒｅｅに格納されている文字列の文字数の合計をｎとするとき，リーフ４０３の数がｎなので，リーフ以外のノードの数はｎ−１個以下である。したがって，ｓｕｆｆｉｘ  ｔｒｅｅのノード数は２ｎ−１個以下で，Ｏ（ｎ）である。
【００２８】
●パスラベル
Ｓｕｆｆｉｘ  ｔｒｅｅ中のノード４０７のパスラベルとは，ルートノード４０２からこのノード４０７にいたるパス４０８上のエッジのラベルを，連結して得られる文字列である。本明細書では，「パスラベルがｓのノード」と言った場合には，パスラベルがｓで，かつルートノード４０２からそのノード４０７までのパス上に空文字列４０６をラベルとするエッジが存在しないノードを表すこととする。
【００２９】
●Ｓｕｆｆｉｘ  ｌｉｎｋ
ノードｖのパスラベルが，ある文字ａとある文字列ｓによりａｓと表現できるとき，パスラベルをｓとするノードへのポインタをｓｕｆｆｉｘ  ｌｉｎｋと呼ぶ。本明細書では，ノードｖのｓｕｆｆｉｘ  ｌｉｎｋを，該ノードｖに直接至るエッジのラベルがεでない場合に定義し，ｓｕｆｆｉｘｌｉｎｋ（ｖ）と表記する。ノードｖのパスラベルがａｓならば，ｓｕｆｆｉｘｌｉｎｋ（ｖ）が指し示すべきノード，すなわち文字列ｓをパスラベルとするノードは必ず存在することが知られている（Ｇｕｓｆｉｅｌｄ，  Ｄ．，  Ａｌｇｏｒｉｔｈｍｓ  ｏｎ  Ｓｔｒｉｎｇｓ，  Ｔｒｅｅｓ，  ａｎｄ  Ｓｅｑｕｅｎｃｅｓ：  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｂｉｏｌｏｇｙ．  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  Ｎｅｗ  Ｙｏｒｋ，  ｃｈａｐｔｅｒ  ６）。図４の４０９は，ｓｕｆｆｉｘ  ｌｉｎｋの例である。なお，誤解を招く恐れのないときは，「ｓｕｆｆｉｘｌｉｎｋ（ｖ）」という表記を，ｓｕｆｆｉｘｌｉｎｋ（ｖ）が指すノードと同一視する場合がある。
次に，本明細書で特に用いる記号・用語および，本発明の新規な概念について，以下で定義する。
【００３０】
●入力文字列（図３の３０１参照）
本発明の方法に入力として与えられる，塩基配列やアミノ酸配列などの，生体高分子配列。
●Ｎ
本発明の方法を適用すべき入力文字列の文字数の総和。
●ｕ
本発明の方法に与えられるパラメータで，エクソン配列と考えられる最も短い文字列の長さを指定する整数である。
●ｐ（ｖ）
ノードｖのパスラベル。
●ｖ（ｓ）
パスラベルが文字列ｓのノード。
●Ｐ（ｓ）
文字列ｓを部分文字列として含む入力文字列の集合。なお，文字列ｓが文字列ｓ’の部分文字列ならば，Ｐ（ｓ）⊇Ｐ（ｓ’）が成り立つ。
【００３１】
●ＭＵＭ（図３の３０３参照）
上述の条件（Ｍ１）−（Ｍ５）を満たす文字列。
●ＵＥＢ（図３の３０５参照）
上述の条件（Ａ１）−（Ａ６）を満たす文字列。
●右ＭＵＭ（図３の３０２参照）
右ＭＵＭとは，次の条件（Ｒ１）−（Ｒ４）を満たす文字列である。
（Ｒ１）  １つ以上の入力文字列の部分文字列である。
（Ｒ２）  長さはｕ以上である。
（Ｒ３）  各入力文字列には，高々１回しか出現しない。
（Ｒ４）  右ＭＵＭ  ｒは，任意の文字ａに対してＰ（ｒ）≠Ｐ（ｒａ）を満たす。すなわち，右ＭＵＭは，この右ＭＵＭを部分文字列として共有するすべての入力文字列を維持したまま右側へ延長することはできない。
【００３２】
なお，任意の右ＭＵＭ  ｒに対し，Ｐ（ｓｒ）＝Ｐ（ｒ）を満たす空文字列かも知れない最長の文字列ｓをとることができ，ｓｒは（Ｍ１）−（Ｍ５）を満たすので，ＭＵＭである。したがって，次の性質（Ｒ５）が成り立つ。
（Ｒ５）  任意の右ＭＵＭ  ｒについて，ｒをｓｕｆｆｉｘとするＭＵＭ  ｍで，Ｐ（ｍ）＝Ｐ（ｒ）を満たすものが存在する。
【００３３】
また，右ＭＵＭ  ｒがあるＭＵＭ  ｍのｐｒｅｆｉｘであると仮定する。このとき，任意の文字ａについてＰ（ａｍ）≠Ｐ（ｍ）よりＰ（ａｍ）⊂Ｐ（ｍ）だから，Ｐ（ｍ）の入力文字列のうち，少なくとも１つの入力文字列ｉはＰ（ａｍ）に属さない。ｒは，ｍを含む入力文字列にはｍのｐｒｅｆｉｘとしてしか現れないから，入力文字列ｉ上のｒの左には文字ａがないため，Ｐ（ａｒ）に属さない。しかし，ｉ∈Ｐ（ｍ）⊆Ｐ（ｒ）。したがって，Ｐ（ａｒ）≠Ｐ（ｒ）であり，ｒは（Ｍ５）を満たす。つまり，右ＭＵＭについて，次の性質（Ｒ６）が成り立つ。
（Ｒ６）  ＭＵＭのｐｒｅｆｉｘである右ＭＵＭは，ＭＵＭである。
【００３４】
●左ＭＵＭ
左ＭＵＭとは，次の条件（Ｌ１）−（Ｌ４）を満たす文字列である。
（Ｌ１）  １つ以上の入力文字列の部分文字列である。
（Ｌ２）  長さはｕ以上である。
（Ｌ３）  各入力文字列には，高々１回しか出現しない。
（Ｌ４）  左ＭＵＭ  ｌは，任意の文字ａに対してＰ（ｌ）≠Ｐ（ａｌ）  を満たす。すなわち，左ＭＵＭは，この左ＭＵＭを部分文字列として共有するすべての文字列を維持したまま左側へ延長することはできない。
【００３５】
●右ＵＥＢ−ｈｏｌｄｅｒ（図３の３０４参照）
右ＵＥＢ−ｈｏｌｄｅｒとは，次の条件（Ｈ１）−（Ｈ３）を満たす文字列である。
（Ｈ１）  右ＭＵＭである。
（Ｈ２）  次の（Ｈ２ａ），（Ｈ２ｂ）のうち，どちらかの条件を満たす。
（Ｈ２ａ）  ＭＵＭである。
（Ｈ２ｂ）  あるＭＵＭ  ｍが存在し，ｍｈが少なくとも１つの入力文字列の部分文字列となるような，文字列ｈである。
（Ｈ３）  右ＭＵＭを真のｐｒｅｆｉｘとして持たない。
【００３６】
上述したように，本発明では右ＭＵＭ，左ＭＵＭ又はＭＵＭ，右ＵＥＢ−ｈｏｌｄｅｒを順次抽出し，それらを利用してＵＥＢを抽出する。図５は，本発明による処理の全体を示すフローチャートである。以下では，図５を参照して，右ＭＵＭ，左ＭＵＭ，ＭＵＭ，右ＵＥＢ−ｈｏｌｄｅｒ，ＵＥＢを抽出する方法を説明する。
【００３７】
■Ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔの構築（ステップＳ５０１）
本発明の方法では，まず，入力文字列に基づきｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを構築する。Ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ  は，Ｕｋｋｏｎｅｎ  のアルゴリズム（Ｇｕｓｆｉｅｌｄ，  Ｄ．，  Ａｌｇｏｒｉｔｈｍｓ  ｏｎ  Ｓｔｒｉｎｇｓ，  Ｔｒｅｅｓ，  ａｎｄ  Ｓｅｑｕｅｎｃｅｓ：  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｂｉｏｌｏｇｙ．  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  Ｎｅｗ  Ｙｏｒｋ，  ｃｈａｐｔｅｒ  ６）を用いて，Ｏ（Ｎ）で，全ｓｕｆｆｉｘ  ｌｉｎｋを設定する工程を含めて構築可能である。
【００３８】
本発明の方法は，こののち，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ上の深さ優先探査を繰り返し実行する。以下の説明では特に断らない限り，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ上の深さ優先探査において，ラベルが空文字列であるエッジとそのエッジが指し示すリーフを無視する。
【００３９】
■右ＭＵＭの抽出（ステップＳ５０２）
本発明の方法は，右ＭＵＭを以下の（ｒ１）−（ｒ３）の方法により抽出する。
（ｒ１）  Ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを用いて，Ｇｕｓｆｉｅｌｄ，  Ｄ．，  Ａｌｇｏｒｉｔｈｍｓ  ｏｎ  Ｓｔｒｉｎｇｓ，  Ｔｒｅｅｓ，  ａｎｄ  Ｓｅｑｕｅｎｃｅｓ：  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｂｉｏｌｏｇｙ．  Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  Ｎｅｗ  Ｙｏｒｋ，  ｃｈａｐｔｅｒ  ９記載の方法により，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔの任意のノードｖの部分木に同一の入力文字列由来のリーフが存在するとき，かつそのときに限り，ノードｖの部分木の少なくとも１つのノードｖ’について，ｈ（ｖ’）＞０となるように，ｈ（ｖ）の値を設定可能である。この（ｒ１）のステップはＯ（Ｎ）で完了できることが知られている。
（ｒ２）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔの任意のノードｖについて，変数ｄ（ｖ）を設け，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを深さ優先探査する。この深さ優先探査では，ラベルが空文字列であるエッジと，そのエッジの指し示すリーフも探査する。探査の過程で遭遇したノードｖがリーフか否かにより，（ｒ２ａ）または（ｒ２ｂ）の処理を行なう。
（ｒ２ａ）ノードｖがリーフのとき，１を報告する。もし，ノードｖに至るエッジのラベルが空文字列でなければ，ｄ（ｖ）を１にセットする。
（ｒ２ｂ）ノードｖがリーフでないときは，まず部分木それぞれの深さ優先探査を行なう。少なくとも１つの部分木の深さ優先探査で−１との報告があった場合およびｈ（ｖ）≠０の場合は，ｄ（ｖ）＝０とし−１を報告する。これ以外の場合，部分木の探査で報告されたそれぞれの部分木のリーフ数の和をｄ（ｖ）にセットし，セットした値を報告する。
（ｒ３）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを再び深さ優先探査し，次の（ｒ３ａ）および（ｒ３ｂ）を満足するノードｖに出会ったとき，そのノードに「右ＭＵＭである」との印をつける。なお，（ｒ３ａ）の条件を満たすか否か判定するために必要なパスラベル長は，探査の際にルートノードからｖまでのパス上のエッジ長の和を保持することで，各ノードごとに定数時間で計算できる。なお，（ｒ３）の深さ優先探査では，ラベルが空文字列であるエッジと，そのエッジの指し示すリーフは無視する。
（ｒ３ａ）パスラベルの長さがｕ以上
（ｒ３ｂ）ｄ（ｖ）＞０
（ｒ１）−（ｒ３）の処理が完了した時点で，「右ＭＵＭである」と印がついたノードのパスラベルは右ＭＵＭであり，かつそれらだけが右ＭＵＭである。その理由を述べる。
【００４０】
まず，（ｒ１）によって，ノードｖの部分木に同一の入力文字列由来のリーフが存在するとき，かつそのときに限り，ノードｖの部分木の少なくとも１つのノードｖ’について，ｈ（ｖ’）＞０となるように，ｈ（ｖ）の値が設定される。したがって，（ｒ２）において，各ノードｖの変数ｄ（ｖ）は，以下の条件（ｄ１）および（ｄ２）を満足するように設定される。
（ｄ１）ノードｖのパスラベルｐ（ｖ）が，２回以上出現する入力文字列が存在するときはｄ（ｖ）＝０。
（ｄ２）ノードｖのパスラベルｐ（ｖ）が，任意の入力文字列に高々１回しか出現しない場合には，ｄ（ｖ）≠０。
【００４１】
ｄ（ｖ）の値が（ｄ１）と（ｄ２）を満足することを踏まえ，本発明の方法で「右ＭＵＭである」と印がついたノードのパスラベルが，右ＭＵＭの条件（Ｒ１）−（Ｒ４）を満足することを示す。
（Ｒ１）について：
ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ  の任意のノードのパスラベルは，少なくとも１つの入力文字列のｓｕｆｆｉｘのｐｒｅｆｉｘである。つまり，少なくとも１つの文字列の部分文字列である。したがって，（Ｒ１）は満たされる。
（Ｒ２）について：
本発明の方法で「右ＭＵＭである」と印がつくノードは，長さｕ以上のパスラベルを持つノードだけである。したがって，（Ｒ２）も満たされる。
（Ｒ３）について：
ｄ（ｖ）＞０なるノードだけに「右ＭＵＭ」であるとの印がつく。ｄ（ｖ）の性質より，これらのノードｖのパスラベルは，各入力文字列中に高々１回しか出現しない。したがって，（Ｒ３）も満たされる。
（Ｒ４）について：
「右ＭＵＭ」であるとの印がついたノードｖのパスラベルｐ（ｖ）について，どのように文字ａを選んでも，ある入力文字列ｉ∈Ｐ（ｖ）が存在し，その入力文字列ｉはｐ（ｖ）ａを部分文字列として持たない。もし，そのような入力文字列ｉが存在しないなら，ｖから出るエッジはすべてａで始まるため，ｓｕｆｆｉｘ  ｔｒｅｅの条件（Ｓ４）に反するからである。したがって，ｐ（ｖ）は（Ｒ４）を満足する。
さらに，本発明の方法で右ＭＵＭの印がついたノードのパスラベルの文字列でなければ，（Ｒ１）−（Ｒ４）のどれかの条件を満足しないことを示す。
【００４２】
まず，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔのパスラベルのｐｒｅｆｉｘとして現れない文字列は，どの入力文字列の部分文字列でもないから，（Ｒ１）に反する。
次に，ノードのパスラベルのｐｒｅｆｉｘとなっている文字列ｒに，対応するノードｖ（ｒ）が存在しないと仮定する。このとき，ある文字ａについてＰ（ｒ）＝Ｐ（ｒａ）である。なぜなら，こうした文字ａが存在しないならば，ｒをｓｕｆｆｉｘとする入力文字列が存在するか，ａでない文字ｂについてｒｂを含む入力文字列が存在することを意味し，どちらの場合もｖ（ｒ）が存在しないとの仮定に反するからである。よって，Ｐ（ｒ）＝Ｐ（ｒａ）なるａが存在するからｒは（Ｒ４）を満足しない。
【００４３】
さらに，本発明の方法は，パスラベルが長さｕ未満のノードには印をつけないが，これらのノードのパスラベルは（Ｒ２）を満足しない。しかも，本発明の方法はｄ（ｖ）＝０のノードには印をつけないが，それらは少なくとも１つの入力文字列に２回以上出現する部分文字列である。ゆえに，（Ｒ３）を満足しない。
【００４４】
以上で検討した以外に，（ｒ１）−（ｒ３）の方法で「右ＭＵＭである」と印がつかないノードのパスラベル以外の文字列は存在しない。つまり（ｒ１）−（ｒ３）の方法ですべての右ＭＵＭに対して，対応するノードに過不足なく「右ＭＵＭである」と印をつけることができる。
【００４５】
■左ＭＵＭの抽出（ステップＳ５０３）
ステップＳ５０１でｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを構築し，ステップＳ５０２で右ＭＵＭを抽出したのと同様の方法で，左ＭＵＭを抽出する。なお，ステップＳ５０４によりＭＵＭを抽出する場合，左ＭＵＭを抽出するステップＳ５０３は行なわなくてもよい。
【００４６】
ステップＳ５０３では，左ＭＵＭを抽出するために，すべての入力文字列を逆順に見た文字列について，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ’を構築する。例えば，入力文字列がＡＴＡＴＧとＴＴＡＧＴＡの場合は，これらを逆順にして得られるＧＴＡＴＡとＡＴＧＡＴＴについて，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ’を構築する。そして，「ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ」を「ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ’」に，「右ＭＵＭ」を「左ＭＵＭ」に読み替えて（ｒ１）−（ｒ３）を実行する。この方法で，左ＭＵＭを過不足無く抽出できるのは，ステップＳ５０２で過不足なく右ＭＵＭが抽出されることから明らかである。
【００４７】
■ＭＵＭの抽出（ステップＳ５０４）
ＭＵＭを抽出する方法について述べる。なお，ステップＳ５０３により左ＭＵＭの抽出を行なった場合，ＭＵＭを抽出するステップＳ５０４は行なわなくてもよい。
【００４８】
全てのＭＵＭは，（Ｍ１）−（Ｍ４）より（Ｒ１）−（Ｒ４）を満たし，右ＭＵＭである。右ＭＵＭのノードには既に上記の方法で「右ＭＵＭである」と印がついているので，ＭＵＭを抽出するためには（Ｍ５）を満足する右ＭＵＭをパスラベルとするノードの中から，ＭＵＭをパスラベルとするノードを選び「ＭＵＭである」と印をつければよい。
【００４９】
最も単純な方法は，右ＭＵＭに対応する全てのノードｖについて，ｖのパスラベルを部分文字列として含む入力文字列の集合すなわちＰ（ｐ（ｖ））を記録し，任意の文字ａについてＰ（ａｐ（ｖ））≠Ｐ（ｐ（ｖ））か否か調べる方法である。ところが，この方法では計算時間をＯ（Ｎ）とできない。計算時間がＯ（Ｎ）を超える例を以下に示す。
【００５０】
文字列ｔ（ｎ，ｋ）を，長さがｎでｋ番目の文字がＡ，それ以外の文字がＴである文字列とし，入力文字列集合６０１が［ｔ（ｎ，ｋ）：０≦ｋ≦ｎ−１］である場合を考える。ｎ＝５の例を図６に示す。このとき，０≦ｋ≦ｋ’−１，  １≦ｋ’≦ｎである任意のｋ，ｋ’について，ｕ＝１とすれば，ｔ（ｋ’，ｋ）  ６０２は（Ｍ１）−（Ｍ５）を満たし，ＭＵＭになる。ｔ（ｋ’，ｋ）は先頭と末尾のＡの数の合計に等しい数の入力文字列を除き，すべての入力文字列上に存在するから，ｎ−（ｋ’−１）個の入力文字列上に存在する。この例の入力文字列集合６０１の総文字数はＮ＝ｎ＾２であることを考慮すれば，ＭＵＭの総数は式（１）よりＮ／２より多く，全てのＭＵＭについてＰ（ｐ（ｖ））を求めるだけで，Ｎに入力文字列数を乗じた数のオーダーの計算時間が必要とわかる。したがって，処理時間をＯ（Ｎ）に抑えることができない。
【００５１】
【数１】
2004152023.tif 000003
【００５２】
本発明は，Ｏ（Ｎ）の処理時間で，（Ｍ５）を満たす右ＭＵＭと印のついたノードに，過不足無く「ＭＵＭである」と印をつける方法を提供する。まず，入力文字列のｐｒｅｆｉｘになっているＭＵＭのノードに，次の方法（ｍ１）で「ＭＵＭである」と印をつける。
（ｍ１）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを深さ優先探査し，ノードに出会ったら，以下の処理を行なう。この深さ優先探査は，ラベルがεのエッジおよびその先のリーフも探査の対象とする。
（ｍ１ａ）  そのノードｖがリーフなら，そのリーフ（ｉ，ｊ）において，ｊ＝０のとき，ｔｒｕｅを返す。このとき，ｖに右ＭＵＭの印がついているならば，ｖに「ＭＵＭである」と印をつける。ｐ（ｖ）がどの入力文字列のｐｒｅｆｉｘでもなかったら，印をつけずにｆａｌｓｅを返す。なお，ｊ＝０のとき，リーフ（ｉ，ｊ）のパスラベルは入力文字列ｉに一致し，ルートノードからリーフ（ｉ，ｊ）に至るパス上の任意のノードのパスラベルは，入力文字列ｉのｐｒｅｆｉｘである。
（ｍ１ｂ）  そのノードｖがリーフでなければ，先に全ての部分木の探査を行なう。１つでもｔｒｕｅを返す部分木があり，ｖに右ＭＵＭの印がついているならば，ｖに「ＭＵＭである」と印をつけてｔｒｕｅを返す。それ以外の場合，印をつけずにｆａｌｓｅを返す。右ＭＵＭ  ｒが，少なくとも１つの入力文字列のｐｒｅｆｉｘとなっているならば（Ｍ５）を満足し，そのようなｒには（ｍ１）の方法で「ＭＵＭである」と過不足なく印がつく。
【００５３】
次に，どの入力文字列のｐｒｅｆｉｘでもない右ＭＵＭをパスラベルとするノードのうち，ＭＵＭをパスラベルとするノードに（ｍ２）−（ｍ７）の方法で印をつける。
（ｍ２）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔの全てのノードｖについて，ｖに直接至るエッジのラベルがεでないときに，変数Ｃ（ｖ），  Ｎ（ｖ）を用意し，０で初期化する。
（ｍ３）  深さ優先探査で，出会ったノードｖについて，変数Ｃ（ｓｕｆｆｉｘｌｉｎｋ（ｖ））に１を加える。
（ｍ４）  再び深さ優先探査で，出会ったノードｖについて，ｖに「右ＭＵＭである」と印があり，Ｃ（ｖ）＝０であれば，ｖに「ＭＵＭである」と印をつける。
（ｍ５）  再び深さ優先探査で，出会ったノードｖについて，そのノードをルートノードとする部分木のｖを含む全ノードｖ’のＣ（ｖ’）の値の合計値を求め，Ｃ（ｖ）をその合計値にセットする。
（ｍ６）  再び深さ優先探査で，出会ったノードｖについて，そのノードをルートノードとする部分木のｖを含む全ノードで該ノードに至るエッジのパスラベルがεでないものの数を求め，Ｎ（ｖ）にセットする。
（ｍ７）  再び深さ優先探査で，出会ったノードｖについて，ｓｕｆｆｉｘｌｉｎｋ（ｖ）が右ＭＵＭへのポインタであり，Ｎ（ｖ）≠Ｃ（ｓｕｆｆｉｘｌｉｎｋ（ｖ））ならば，ｓｕｆｆｉｘｌｉｎｋ（ｖ）の指し示すノードに「ＭＵＭである」との印をつける。
【００５４】
（ｍ４）で，ＭＵＭである右ＭＵＭ  ｒをパスラベルとするノードｖ（ｒ）に「ＭＵＭである」と印がつけば，ｒはＭＵＭであることを説明する。まず，ｒがある入力文字列のｐｒｅｆｉｘならばｒはＣ（ｖ（ｒ））の値に関わらずＭＵＭである。どの入力文字列のｐｒｅｆｉｘでもないｒについて検討する。このとき，ａｒが少なくとも１つの入力文字列の部分文字列であるように，文字ａを選ぶことができる。Ｐ（ａｒ）＝Ｐ（ａｒｓ）を満たす最長の文字列をｓとする。このとき，ａｒｓは（Ｒ１）と（Ｒ４）を満たし，ｒを部分文字列とするから（Ｒ２）と（Ｒ３）も満たすので右ＭＵＭである。ｓ＝εと仮定すれば，ｖ（ａｒ）が存在してｖ（ｒ）にｓｕｆｆｉｘ  ｌｉｎｋを持ちＣ（ｖ（ｒ））≠０だから，（ｍ４）でｖ（ｒ）に印がつくことに矛盾するのでｓ≠εである。ｓの先頭の文字をｂとする。ｒが右ＭＵＭだから，Ｐ（ｒｂ）≠Ｐ（ｒ）。ｒが少なくとも１つの入力文字列のｓｕｆｆｉｘであるとすれば，ｒはどの入力文字列のｐｒｅｆｉｘでもないから，ｒより１文字長いｓｕｆｆｉｘをパスラベルとするノードからｖ（ｒ）にｓｕｆｆｉｘｌｉｎｋがあるはずでＣ（ｖ（ｒ））≠０だから，（ｍ４）でｖ（ｒ）に印がつくことに矛盾。よって，ｂと異なる文字ｂ’を，ｒｂ’が少なくとも１つの入力文字列の部分文字列となるように選べる。Ｐ（ｒｂ）⊇Ｐ（ａｒｓ）＝Ｐ（ａｒ）であることと，ｒｂ’はｒｂを部分文字列とする入力文字列上には存在しないことから，ｒｂ’はａｒを部分文字列とする任意の入力文字列上に存在しない。しかし，ｒはどの入力のｐｒｅｆｉｘでもないから，ａ’ｒｂ’が少なくとも１つの入力文字列の部分文字列になるようにａでない文字ａ’を選べる。したがって，右ＭＵＭ  ｒは，ａ≠ａ’より（Ｍ５）を満たし，ＭＵＭであることがわかる。
【００５５】
（ｍ７）で印がついたノードのパスラベルのうち，どの入力文字列のｐｒｅｆｉｘでもない文字列もＭＵＭであることを説明する。これ以降，Ｎ（ｖ（ａｒ）），Ｃ（ｖ（ｒ））は，（ｍ１）−（ｍ６）が完了し，（ｍ７）のステップを実行するときの値とする。まず，ある文字列ａｒをパスラベルとするノードｖ（ａｒ）に関して，Ｎ（ｖ（ａｒ））＝Ｃ（ｖ（ｒ））が成り立つときに，かつそのときに限り，Ｐ（ａｒ）＝Ｐ（ｒ）であることを説明する。
【００５６】
はじめに，Ｐ（ａｒ）＝Ｐ（ｒ）が成り立つときＮ（ｖ（ａｒ））＝Ｃ（ｖ（ｒ））である理由を述べる。まず，Ｐ（ａｒ）＝Ｐ（ｒ）を仮定すると，Ｎ（ｖ（ａｒ））≧Ｃ（ｖ（ｒ））であることを説明する。ｖ（ｒ）の部分木の，あるノードｗについて，Ｃ（ｗ）がｖ（ａｒ）の部分木にないノードｗ’からのｓｕｆｆｉｘ  ｌｉｎｋにより（ｍ３）において増えたとする。このとき，ａでない文字ｂが存在しｐ（ｗ’）＝ｂｒｓ。一方，Ｐ（ｂｒｓ）に属する任意の入力文字列は，ａ≠ｂよりａｒを部分文字列として持たない。したがって，Ｐ（ｂｒｓ）⊆Ｐ（ｒ）よりＰ（ａｒ）≠Ｐ（ｒ）であり，仮定に矛盾する。つまり，Ｃ（ｖ（ｒ））はｖ（ａｒ）の部分木のノードからのｓｕｆｆｉｘ  ｌｉｎｋ以外で増えることができないから，Ｎ（ｖ（ａｒ））≧Ｃ（ｖ（ｒ））。ところが，次に述べる理由により，Ｎ（ｖ（ａｒ））≦Ｃ（ｖ（ｒ））である。ｖ（ａｒ）の部分木の任意のノードｗのパスラベルは，ある文字列ｓを用いてａｒｓと書ける。このとき，ｓｕｆｆｉｘｌｉｎｋ（ｗ）はｖ（ｒｓ）を指しており，ｖ（ｒｓ）は，ｖ（ｒ）の部分木のノードである。よって，Ｎ（ｖ（ａｒ））個あるｖ（ａｒ）の部分木の任意のノード１つにつき，ｖ（ｒ）の部分木のどれか１つのノードｗ’についてＣ（ｗ’）が（ｍ３）のステップで１つ増える。Ｃ（ｖ（ｒ））は，（ｍ５）が終了した時点でｖ（ｒ）の部分木の全てのノードｗ’のＣ（ｗ’）が（ｍ３）で増やされた回数の総和に更新されるから，Ｎ（ｖ（ａｒ））≦Ｃ（ｖ（ｒ））になる。したがって，Ｎ（ｖ（ａｒ））＝Ｃ（ｖ（ｒ））が成り立つ。
【００５７】
次に，Ｎ（ｖ（ａｒ））＝Ｃ（ｖ（ｒ））が成り立つときＰ（ａｒ）＝Ｐ（ｒ）である理由を述べる。Ｐ（ａｒ）⊆Ｐ（ｒ）は明らか。Ｐ（ｒ）に属しＰ（ａｒ）に属さない入力文字列ｉの存在を仮定する。ｒはどの入力文字列のｐｒｅｆｉｘでもないから，入力文字列ｉ上ではｒの左にａでない文字ｂが存在する。ｖ（ａｒ），ｖ（ｂｒ）をルートノードとする部分木の任意のノードは，ｖ（ｒ）をルートノードとする部分木のノードへのｓｕｆｆｉｘ  ｌｉｎｋを持つから，Ｃ（ｖ（ｒ））≧Ｎ（ｖ（ａｒ））＋Ｎ（ｖ（ｂｒ））が成り立つ。ところが，ｂｒは入力文字列ｉ上の部分文字列だから，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔにｂｒをパスラベルのｐｒｅｆｉｘとするノードが少なくとも１つ存在する。よって，Ｎ（ｖ（ｂｒ））＞０。したがって，Ｃ（ｖ（ｒ））＞Ｎ（ｖ（ａｒ））。これはＣ（ｖ（ｒ））＝Ｎ（ｖ（ａｒ））に矛盾する。ゆえに，Ｐ（ｒ）に属しＰ（ａｒ）に属さないような入力文字列ｉが存在すると仮定したのが誤りで，Ｐ（ｒ）＝Ｐ（ａｒ）が成り立つとわかる。
【００５８】
（ｍ７）では，Ｎ（ｖ）≠Ｃ（ｓｕｆｆｉｘｌｉｎｋ（ｖ））のとき，ｓｕｆｆｉｘｌｉｎｋ（ｖ）が指し示すノードｗが右ＭＵＭをパスラベルとするなら，ｗに「ＭＵＭである」と印をつけている。ｒ＝ｐ（ｗ）とすれば，ある文字ａが存在してａｒがｖのパスラベルである。すなわち，（ｍ７）ではＮ（ｖ（ａｒ））≠Ｃ（ｖ（ｒ））なる右ＭＵＭのノードｖ（ｒ）にのみ印がつくが，ｒがどの入力文字列のｐｒｅｆｉｘでもなければ，Ｐ（ａｒ）≠Ｐ（ｒ）よりｒはＭＵＭである。一方，ｒが少なくとも１つの入力文字列のｐｒｅｆｉｘならば，ｒがＭＵＭであることは自明。つまり，（ｍ７）でもＭＵＭをパスラベルとするノードにしか「ＭＵＭである」と印をつけないことがわかる。
【００５９】
逆に，（ｍ１）−（ｍ７）の方法で印が付かないＭＵＭは存在しないことを示す。まず，入力文字列のｐｒｅｆｉｘであるＭＵＭをパスラベルにもち，（ｍ１）で印がつかないノードが存在しない。次に，どの入力文字列のｐｒｅｆｉｘでもないＭＵＭ  ｍについて考察する。このようなｍをパスラベルとするノードｖ（ｍ）を指し示すｓｕｆｆｉｘ  ｌｉｎｋが存在しないときは，（ｍ４）で印がつく。一方，ノードｖ（ｍ）を指し示すｓｕｆｆｉｘ  ｌｉｎｋが存在するときは，そのｓｕｆｆｉｘ  ｌｉｎｋの起点となっているノードに（ｍ７）の深さ優先探査で出会ったときにｖ（ｍ）に「ＭＵＭである」と印がつく。以上の理由により，すべてのＭＵＭに（ｍ１）−（ｍ７）の方法で「ＭＵＭである」と印がつく。
【００６０】
■ＭＵＭ末端位置の抽出（ステップＳ５０５）
ステップＳ５０２で抽出した右ＭＵＭの情報と，ステップＳ５０３で抽出した左ＭＵＭの情報またはステップＳ５０４で抽出したＭＵＭの情報を用いて，ステップＳ５０５で２次元配列Ｈｅａｄ，Ｔａｉｌを以下のように設定する。なお，Ｈｅａｄ，  Ｔａｉｌは，入力文字列ｉと該入力文字列の長さよりも小さな非負整数ｊに対して値を持つ。
Ｈｅａｄ［ｉ，ｊ］  ：
入力文字列ｉのｊ番目の塩基から始まる部分文字列に，ＭＵＭであるものが存在すれば１。それ以外の場合は０。（図７参照）
Ｔａｉｌ［ｉ，ｊ］  ：
入力文字列ｉのｊ番目の塩基で終わる部分文字列に，ＭＵＭであるものが存在すれば１。それ以外の場合は０。（図７参照）
【００６１】
まず，Ｔａｉｌの値を設定する方法について述べる。本発明の方法では，Ｔａｉｌの値を設定するにあたり，ＭＵＭの位置を直接計算する代わりに，他の右ＭＵＭをｓｕｆｆｉｘとして持たない右ＭＵＭ  ｒの位置を計算する。そのような任意のｒについて，ｒが入力文字列ｉのｊ番目塩基を末尾とする部分文字列であるなら，Ｔａｉｌ［ｉ，ｊ］  ７０２に，１を書き込む。このような，他の右ＭＵＭをｓｕｆｆｉｘとしない右ＭＵＭ  ｒ  （以下，極小右ＭＵＭと呼ぶ）の終了位置の集合と，全てのＭＵＭの終了位置の集合は等しい。その理由は，全ての右ＭＵＭ  ｒには（Ｒ５）よりｒをｓｕｆｆｉｘ  としＰ（ｒ）＝Ｐ（ｍ）であるＭＵＭ  ｍが存在する一方，全てのＭＵＭ  ｍは極小右ＭＵＭ  ｒをｓｕｆｆｉｘとして持ち，Ｐ（ｍ）⊆Ｐ（ｒ）  が成り立つからである。以上を踏まえ，次の（ｔ１）−（ｔ４）の方法で，全ての右ＭＵＭの末端に対応するＴａｉｌ［ｉ，ｊ］  ７０２を１に設定することができる。
（ｔ１）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを，深さ優先探査し，「右ＭＵＭである」と印があるノードｖについて，ｓｕｆｆｉｘｌｉｎｋ（ｖ）が指し示すノードが右ＭＵＭでないとき，ｖに「極小右ＭＵＭ」と印を付ける。
（ｔ２）  ２次元配列Ｔａｉｌ  ７０１の全ての要素を０で初期化。
３＿ｒｉｇｈｔ＿ＭＵＭを空リストで初期化する。
（ｔ４）  再びｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを深さ優先探査し，出会ったノードｖに対し（ｔ４ａ），（ｔ４ｂ）の処理を行なう。この深さ優先探査では，ラベルがεであるエッジの終端にあるノードも含めて全ノードを探査する。
（ｔ４ａ）  ｖに「極小右ＭＵＭである」と印がついている場合には，リストｍｉｎｉｍａｌ＿ｒｉｇｈｔ＿ＭＵＭの末尾に，ｖのパスラベルの長さ｜ｐ（ｖ）｜を追加する。なお，リストｍｉｎｉｍａｌ＿ｒｉｇｈｔ＿ＭＵＭに追加した値は，ノードｖをルートノードとする部分木の処理が終了した時点で削除する。この削除の操作は，単にｍｉｎｉｍａｌ＿ｒｉｇｈｔ＿ＭＵＭの末尾の要素を削除するだけで実現できる。
（ｔ４ｂ）  ｖがリーフ（ｉ，ｊ）のとき，リストｍｉｎｉｍａｌ＿ｒｉｇｈｔ＿ＭＵＭの任意の要素ｋについて，Ｔａｉｌ［ｉ，ｊ＋ｋ−１］  ７０１を１に設定する。
【００６２】
（ｔ１）で，極小右ＭＵＭのノードに，過不足無く印がつく。よって，（ｔ２）−（ｔ４）で，入力文字列ｉのｊ番目の文字で終了する極小右ＭＵＭが存在するときに，かつそのときに限り，Ｔａｉｌ［ｉ，ｊ］に１を書き込む。逆に，このようなｉ，ｊ以外では，Ｔａｉｌ［ｉ，ｊ］は１にならない。この方法で，同一のｉ，ｊに対し，２回以上Ｔａｉｌ［ｉ，ｊ］が更新されることはないから，（ｔ１）−（ｔ４）はＯ（Ｎ）で完了できる。
【００６３】
なお，極小右ＭＵＭの位置のみを計算するのではなく，全てのＭＵＭ  ｍや右ＭＵＭ  ｒについて，それらが出現するすべての入力文字列ｉについてｍやｒの最後の文字がｊ番目の文字のときＴａｉｌ［ｉ，ｊ］に印をつける方法では，Ｏ（Ｎ）の処理時間では完了できない場合がある。ステップＳ５０４の説明で述べたときの入力文字列集合６０１が，その例となっている。０≦ｋ≦ｋ’−１，  １≦ｋ’≦ｎである任意のｋ，ｋ’について，ｔ（ｋ’，ｋ）  ６０２はＭＵＭであり右ＭＵＭであるが，これらが入力文字列に出現する回数の総和は式（２）で表される。したがって，入力文字列ｉのｊ番目の文字で終了するような全てのｉ，ｊについてＴａｉｌ［ｉ，ｊ］＝１とする処理のステップ数が，Ｎ＾（３／２）のオーダーの計算時間を要する例が存在し，直接ＭＵＭや右ＭＵＭの位置を計算する方法では，Ｏ（Ｎ）の処理時間でＴａｉｌの値を設定するのは不可能とわかる。
【００６４】
【数２】
2004152023.tif 000004
【００６５】
次に，Ｈｅａｄ［ｉ，ｊ］  ７０１を設定する方法を示す。まず，ステップＳ５０３で，左ＭＵＭの抽出が完了している場合に，Ｈｅａｄ［ｉ，ｊ］  ７０１を設定する方法を示す。他の左ＭＵＭをｐｒｅｆｉｘとしない左ＭＵＭを極小左ＭＵＭとする。Ｈｅａｄ［ｉ，ｊ］を設定するためには，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔをｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ’，右ＭＵＭを左ＭＵＭ，極小右ＭＵＭを極小左ＭＵＭ，Ｔａｉｌ［ｉ，ｊ＋ｋ−１］をＨｅａｄ［ｉ，（入力文字列ｉの長さ）−１−（ｊ＋ｋ−１）］と読み替えて，（ｔ１）−（ｔ４）を適用すればよい。この方法で２次元配列Ｈｅａｄを正しく設定できることは，（ｔ１）−（ｔ４）がＴａｉｌを正しく設定することから自明であり，Ｏ（Ｎ）の時間で処理を完了できる。
【００６６】
一方，ステップＳ５０３ではなくステップＳ５０４を実行した場合には，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを深さ優先探査し，「ＭＵＭである」と印がついたノードｖで，ルートノードからｖに至るパス上に別の「ＭＵＭである」と印のついたノードが存在しないノードｖを発見した場合，ｖの部分木内では，ラベルがεのエッジおよびそのエッジの先にあるリーフも対象とする深さ優先探査に変更し，出会った任意のリーフ（ｉ，ｊ）について，Ｈｅａｄ［ｉ，ｊ］  ７０１を１に設定すればよい。この方法で，同一のｉ，ｊの組に対し，２回以上Ｈｅａｄ［ｉ，ｊ］  ７０１が更新されることはないから，（ｔ１）−（ｔ４）はＯ（Ｎ）の処理時間で完了できる。ところで，この方法により他のＭＵＭ  ｍを真のｐｒｅｆｉｘとして持つＭＵＭ  ｍ’の位置は計算されないが，ｍはｍ’のｐｒｅｆｉｘでありＰ（ｍ）⊇Ｐ（ｍ’）だから，ｍ’が入力文字列ｉのｊ番目の文字で始まる部分文字列ならば，ｍもそうであり，Ｈｅａｄ［ｉ，ｊ］は正しく１に設定される。この方法で，入力文字列ｉのｊ番目から始まる任意の文字列がＭＵＭでない場合に，Ｈｅａｄ［ｉ，ｊ］が１にならないことは明らかである。
【００６７】
■右ＵＥＢ−ｈｏｌｄｅｒの抽出（ステップＳ５０６）
以下に述べる方法（ｈ１）−（ｈ３）によって，右ＵＥＢ−ｈｏｌｄｅｒである文字列をパスラベルとするノードに「右ＵＥＢ−ｈｏｌｄｅｒである」と印を付けることができる。事前に，２次元配列Ｔｖを用意する。ＴｖもＨｅａｄ，Ｔａｉｌと同様に，入力文字列ｉと該文字列の長さよりも小さな非負整数ｊに対して値が定義される。
（ｈ１）  Ｔｖの全要素をヌルポインタで初期化する。また，変数ｓｈｏｒｔｅｓｔ＿ｒｉｇｈｔ＿ＭＵＭにヌルポインタを代入する。
（ｈ２）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを深さ優先探査し，出会ったノードｖについて，（ｈ２ａ）と（ｈ２ｂ）の処理を行なう。なお，この深さ優先探査ではラベルがεのエッジとそのエッジが至るリーフも処理の対象とする。
（ｈ２ａ）  ノードｖに「右ＭＵＭである」と印があり，ｓｈｏｒｔｅｓｔ＿ｒｉｇｈｔ＿ＭＵＭがヌルポインタであれば，ｓｈｏｒｔｅｓｔ＿ｒｉｇｈｔ＿ＭＵＭにｖへのポインタを代入する。なお，ｖをルートノードとする部分木の処理が終了した段階で，ｓｈｏｒｔｅｓｔ＿ｒｉｇｈｔ＿ＭＵＭの値はヌルポインタに戻す。
（ｈ２ｂ）  ノードｖがリーフ（ｉ，ｊ）であった場合には，変数ｓｈｏｒｔｅｓｔ＿ｒｉｇｈｔ＿ＭＵＭの値をＴｖ［ｉ，ｊ］に代入する。
（ｈ３）  全ての入力文字列ｉについて，入力文字列のｉの長さより小さい任意の非負整数ｊに対し，次の（ｈ３ａ），（ｈ３ｂ）の条件がともに満たされるとき，Ｔｖ［ｉ，ｊ］が指し示すノードに「右ＵＥＢ−ｈｏｌｄｅｒ」と印を付ける。
（ｈ３ａ）  Ｈｅａｄ［ｉ，ｊ］が１であるか，ｊ≧１かつＴａｉｌ［ｉ，ｊ−１］が１。
（ｈ３ｂ）  Ｔｖ［ｉ，ｊ］がヌルポインタでない。
【００６８】
この方法（ｈ１）−（ｈ３）で，右ＵＥＢ−ｈｏｌｄｅｒをパスラベルとするノードに，かつそれらのノードに限り，「右ＵＥＢ−ｈｏｌｄｅｒである」と印がつくことを示す。まず，（ｈ２）によって，Ｔｖ［ｉ，ｊ］の値は，以下の値に設定される。
（１）  入力文字列ｉのｊ番目の文字から始まる部分文字列である右ＭＵＭ  ｒが存在するなら，ｒをパスラベルとするノードｖへのポインタ。ただし，ルートノードからｖに至るパス上に，ｖ以外に「右ＭＵＭである」と印がついたノードは存在しない。
（２）  入力文字列ｉのｊ番目の文字から始まる部分文字列である右ＭＵＭが存在しないなら，ヌルポインタ。
【００６９】
これを踏まえ，（ｈ３）において，「右ＵＥＢ−ｈｏｌｄｅｒである」と印がついたノードは，実際に右ＵＥＢ−ｈｏｌｄｅｒをパスラベルとするノードであることを示す。
（Ｈ１）について：
右ＭＵＭのノードにしか印をつけないので，そのパスラベルは（Ｈ１）を満たす。
（Ｈ３）について：
Ｔｖ［ｉ，ｊ］がヌルポインタでないとき，Ｔｖ［ｉ，ｊ］は，「右ＭＵＭである」と印が付いたノードｖへのポインタで，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔのルートノードからｖに至るまでのパス上に「右ＭＵＭである」と印がついたノードは存在しない。よって，Ｔｖ［ｉ，ｊ］の指し示すノードのパスラベルは，（Ｈ３）を満足する。
（Ｈ２）について：
Ｈｅａｄ［ｉ，ｊ］が１であるか，ｊ≧１かつＴａｉｌ［ｉ，ｊ−１］が１であるようなＴｖ［ｉ，ｊ］の指すノードにしか印を付けない。したがって，Ｔｖ［ｉ，ｊ］の示すノードのパスラベルをｒとすると，ｒは入力文字列ｉにおいてｊ番目の文字で始まるＭＵＭ  ｍのｐｒｅｆｉｘである右ＭＵＭか，入力文字列ｉにおいてあるＭＵＭの次の文字から始まる右ＭＵＭである。前者の場合，ｒは（Ｒ６）よりＭＵＭである。したがって，（Ｈ２）も満たされる。
【００７０】
次に，ある右ＵＥＢ−ｈｏｌｄｅｒ  ｈについて，本発明の方法によりｖ（ｈ）に右ＵＥＢ−ｈｏｌｄｅｒの印がつかないと仮定する。まず，Ｔｖ［ｉ，ｊ］にｖ（ｈ）へのポインタが入らないと仮定する。このとき，ｈは右ＭＵＭでないか，ｈを真のｐｒｅｆｉｘとする右ＭＵＭが存在する。それぞれ，（Ｈ１），（Ｈ３）よりｈが右ＵＥＢ−ｈｏｌｄｅｒであることに矛盾しＴｖ［ｉ，ｊ］にはｖ（ｈ）へのポインタが入らなければならないことがわかる。それでもｈに「右ＵＥＢ−ｈｏｌｄｅｒである」との印がつかないということは，ｈが入力文字列ｉのｊ番目から始まるような任意のｉ，ｊについて，Ｈｅａｄ［ｉ，ｊ］＝０  かつＴａｉｌ［ｉ，ｊ−１］＝０（ ｊ≧１のとき）ということである。このとき，入力文字列ｉのｊ番目から始まるＭＵＭが存在せず，かつ入力文字列ｉのｊ−１番目の文字を末端とするＭＵＭも存在しないが，そのようなｈは（Ｈ２ａ），（Ｈ２ｂ）をいずれも満たさないため，やはりｈが右ＵＥＢ−ｈｏｌｄｅｒであることに矛盾する。したがって，ｖ（ｈ）に「右ＵＥＢ−ｈｏｌｄｅｒの印がつかない」と仮定したことが誤りであり，本発明の方法はの右ＵＥＢ−ｈｏｌｄｅｒをパスラベルとする全てのノードに印をつけられることがわかる。
【００７１】
■ＵＥＢの抽出（ステップＳ５０７）
ＵＥＢは，次の（ｅ１）−（ｅ３）の方法によって，過不足なく抽出することができる。なお，ＵＥＢを抽出するために，ステップＳ５０５，Ｓ５０６で計算したＨｅａｄ，  Ｔａｉｌ，  Ｔｖの値を利用する。
（ｅ１）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ内の全てのノードｖについて，ｖに至るエッジのラベルがεでないときに，変数ＵＥＢｌｅｎｇｔｈ（ｖ）を設ける。そして，深さ優先探査を行ないＵＥＢｌｅｎｇｔｈ（ｖ）＝｜ｐ（ｖ）｜と初期化する。
（ｅ２）  全ての入力文字列ｉについて，次の（ｅ２ａ）−（ｅ２ｄ）までの処理を行なう。
（ｅ２ａ）  変数ｃを１，変数ｊを入力文字列ｉの長さから１を減じた値で，初期化する。（ｅ２ｂ）  Ｔｖ［ｉ，ｊ］がヌルポインタでなければ，Ｔｖ［ｉ，ｊ］が指し示すノードをｖとし，変数ＵＥＢｌｅｎｇｔｈ（ｖ）の値を，ｃの値７０３とＵＥＢｌｅｎｇｔｈ（ｖ）の値のうち小さい方の値で置き換える。
（ｅ２ｃ）  Ｈｅａｄ［ｉ，ｊ］が１であるか，ｊ≧１かつＴａｉｌ［ｉ，ｊ−１］が１であれば，ｃに１を代入し，それ以外のときはｃに１を加える。
（ｅ２ｄ）  ｊの値から１を減じる。ｊが０以上ならば，（ｅ２ｂ）−（ｅ２ｄ）までの処理を再び行なう。ｊが０より小さければ，入力文字列ｉに関する処理は終了である。
（ｅ３）  ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔを，各ノードｖのパスラベルの長さ｜ｐ（ｖ）｜を求めながら深さ優先探査する。ルートノードからｖに至るパス上の，直接ｖに至るエッジの長さをｅｄｇｅｌｅｎｇｔｈ（ｖ）とする。ノードｖが，次の２つの条件（ｅ３ａ），（ｅ３ｂ）をともに満たすとき，ｖに「ＵＥＢである」と印をつける。
（ｅ３ａ）  ｅｄｇｅｌｅｎｇｔｈ（ｖ）  ＞  ｜ｐ（ｖ）｜−ＵＥＢｌｅｎｇｔｈ（ｖ）
（ｅ３ｂ）  ＵＥＢｌｅｎｇｔｈ（ｖ）≧ｕ
【００７２】
以上の方法で，「ＵＥＢである」と印がついたノードｖの長さＵＥＢｌｅｎｇｔｈ（ｖ）のｐｒｅｆｉｘはＵＥＢであり，かつそれらだけがＵＥＢであることを説明する。その説明に先立ち，（Ａ１）−（Ａ６）の条件が次の（Ｅ１）−（Ｅ６）の条件と等価であることを示す。
（Ｅ１）  ある右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘである。
（Ｅ２）  長さがｕ以上である。
（Ｅ３）  同一文字列には，高々１回しか出現しない。
（Ｅ４）  右でも左でも，ＭＵＭと重ならない。
（Ｅ５）  ＭＵＭを真の部分文字列としない。
（Ｅ６）  （Ｅ１）−（Ｅ５）を満足する文字列の真のｐｒｅｆｉｘにならない。
【００７３】
条件（Ａ１）−（Ａ６）と（Ｅ１）−（Ｅ６）が等価であることを説明する準備として，まず，文字列ｅが（Ｅ１）−（Ｅ３）を満足するなら，ｅは次の性質（Ｅ７）を持つことを示す。
（Ｅ７）  ｅをｐｒｅｆｉｘとする右ＵＥＢ−ｈｏｌｄｅｒ  ｈは一意に決まり，かつその右ＵＥＢ−ｈｏｌｄｅｒ  ｈについて，Ｐ（ｅ）＝Ｐ（ｈ）である。
【００７４】
（Ｅ７）が成り立つことを示すために，（Ｅ１）−（Ｅ３）を満たす文字列ｅについて検討する。（Ｅ１）より，ｅはある右ＵＥＢ−ｈｏｌｄｅｒ  ｈのｐｒｅｆｉｘである。ｅをｐｒｅｆｉｘとする右ＵＥＢ−ｈｏｌｄｅｒ  ｈ’の存在を仮定し，ｈ≠ｈ’とする。（Ｈ３）より，ｈはｈ’の真のｐｒｅｆｉｘではなく，ｈ’もｈの真のｐｒｅｆｉｘではない。しかし，ｅがｈ，ｈ’の共通のｐｒｅｆｉｘだから，図１４に示すように，空文字列かも知れない文字列ｓ，ｓ’，ｓ’’と，ａ≠ａ’なる文字ａ，ａ’が存在してｈ＝ｅｓａｓ’，ｈ’＝ｅｓａ’ｓ’’と書くことができる。このとき，ｅｓはｈ，ｈ’の共通のｐｒｅｆｉｘである。ａ≠ａ’より任意の文字ｂについてＰ（ｅｓｂ）≠Ｐ（ｅｓ）であり，ｅｓは（Ｒ４）を満たす。さらに，ｅｓは右ＵＥＢ−ｈｏｌｄｅｒ  ｈの部分文字列だから（Ｒ１）を満たし，ｅが（Ｅ２）と（Ｅ３）を満たすから（Ｒ２）と（Ｒ３）を満たす。したがって，ｅｓは右ＭＵＭである。ところが，ｈ，ｈ’は右ＵＥＢ−ｈｏｌｄｅｒだから，（Ｈ３）より右ＭＵＭをｐｒｅｆｉｘとして持たないはずである。したがって，ｈ≠ｈ’とした仮定が誤りで，右ＵＥＢ−ｈｏｌｄｅｒは一意であることがわかる。
【００７５】
さらに，ｈが  Ｐ（ｅ）＝Ｐ（ｈ）を満たすことを示す。ｓをＰ（ｅ）＝Ｐ（ｅｓ）を満たす最長の文字列とする。Ｐ（ｅｓ）＝Ｐ（ｅ）⊇Ｐ（ｈ）より，ｅｓはｈを部分文字列とする任意の入力文字列の部分文字列になっている。文字列ｅは，（Ｅ３）よりどの入力文字列上にも高々１回しか出現しないため，ｅｓとｈは，一方が他方のｐｒｅｆｉｘの関係にある。ところで，ｅｓはＰ（ｅ）＝Ｐ（ｅｓ）より（Ｒ１）を満たし，ｅを部分文字列とするから（Ｒ２）と（Ｒ３）を満たし，ｓの定義より（Ｒ４）を満たす。よって，ｅｓは右ＭＵＭである。（Ｈ３）より，ｈは右ＭＵＭをｐｒｅｆｉｘとしないからｈがｅｓのｐｒｅｆｉｘ。よって，Ｐ（ｈ）⊇Ｐ（ｅｓ）＝Ｐ（ｅ）⊇Ｐ（ｈ）だからＰ（ｈ）＝Ｐ（ｅｓ）＝Ｐ（ｅ）である。
すなわち，（Ｅ１）−（Ｅ３）を満たす文字列ｅをｐｒｅｆｉｘとする右ＵＥＢ−ｈｏｌｄｅｒ  ｈは一意であり，Ｐ（ｅ）＝Ｐ（ｈ）であることがわかった。
【００７６】
条件（Ａ１）−（Ａ６）と（Ｅ１）−（Ｅ６）が等価であることを示すにあたり，はじめに，（Ｅ１）−（Ｅ６）を満たす文字列ｅは，（Ａ１）−（Ａ６）を満たすことを示す。
（Ａ１）について：
ｅは（Ｅ１）より右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘだが，任意の右ＵＥＢ−ｈｏｌｄｅｒは右ＭＵＭだから（Ｒ１）を満たすので，少なくとも１つの入力文字列の部分文字列である。したがって，文字列ｅは（Ａ１）を満たす。
（Ａ２）について：
文字列ｅは（Ｅ２）を満たすから，明らかに（Ａ２）を満たす。
（Ａ３）について：
文字列ｅは（Ｅ３）を満たすから，明らかに（Ａ３）を満たす。
（Ａ４）について：
文字列ｅは（Ａ４）を満たすから，明らかに（Ａ４）を満たす。
（Ａ５）について：
文字列ｅは（Ｅ５）を満たすから，明らかに（Ａ５）を満たす
（Ａ６）について：
（Ａ１）−（Ａ５）を満たし，ｅを真の部分文字列とする文字列ｅ’の存在を仮定する。このとき，ある文字列ｓ，ｓ’を用いてｅ’＝ｓｅｓ’と書ける。（Ｅ７）よりｅをｐｒｅｆｉｘとして持つ右ＵＥＢ−ｈｏｌｄｅｒ  ｈが一意に存在する。図１０は，ｅ，ｅ’，ｓ，ｓ’，ｈの関係を図示したものである。
【００７７】
まず，ｓ＝εではないことを説明する。もし，ｓ＝εだと仮定すると，ｅ’＝ｅｓ’だから，ｅはｅ’のｐｒｅｆｉｘであり，ｅ’とｈは一方が他方のｐｒｅｆｉｘの関係にある。さらに，ｅ’≠ｅよりｓ’≠εである。一方，ｈは右ＭＵＭだから（Ｒ５）よりｈをｓｕｆｆｉｘとしＰ（ｈ）＝Ｐ（ｍ）であるＭＵＭ  ｍが存在する。ここで，ｈがｅ’の真のｐｒｅｆｉｘと仮定すれば，ｓ’≠εよりｅ’はｍと左で重なって（Ａ４）に矛盾するか，ｈ＝ｍを部分文字列とし（Ａ５）に矛盾。したがって，ｅ’がｈのｐｒｅｆｉｘである。ところが，ｅ’がｈのｐｒｅｆｉｘならばｅ’は（Ｅ１）を満たし，（Ａ２）−（Ａ５）を満たすから（Ｅ２）−（Ｅ５）を満たすが，ｅはｅ’の真の部分文字列だからｅが（Ｅ６）の条件を満たすことに矛盾する。したがって，ｓ＝εであってはならないことがわかる。
【００７８】
そこで，ｓ≠εを仮定する。ｈがＭＵＭであった場合は，ｅ’はｈの長さにより，ｈと右で重なり（Ａ４）に矛盾するか，ｈを真の部分文字列として含み（Ａ５）と矛盾するかのいずれかとなるため，ｈはＭＵＭではない。つまり，ｈはＭＵＭでない右ＵＥＢ−ｈｏｌｄｅｒ  であるから，（Ｈ２ｂ）よりあるＭＵＭ  ｍ’が存在し，ｍ’ｈが少なくとも１つの入力文字列の部分文字列となる。ところが，（Ｅ７）よりＰ（ｈ）＝Ｐ（ｅ）⊇Ｐ（ｅ’）だから，ｍ’ｈが存在する入力文字列１００１上に，必ずｅ’が存在する。ｓ≠εだから，ｅ’はｍ’と左で重なり（Ａ４）に矛盾するか，ｍ’を部分文字列として含み（Ａ５）に矛盾する。
結局，ｅを真の部分文字列とする文字列ｅ’を（Ａ１）−（Ａ５）を満たすようにとれば，必ず矛盾が生じるとわかる。したがって，ｅは（Ａ６）を満たす。
【００７９】
次に，（Ａ１）−（Ａ６）を満たす文字列ｅは，（Ｅ１）−（Ｅ６）を満たすことを示す。
（Ｅ１）について：
文字列ｓを，Ｐ（ｅ）＝Ｐ（ｅｓ）なる最長の文字列とする。このｅｓが，（Ｈ１）−（Ｈ３）を満たし，右ＵＥＢ−ｈｏｌｄｅｒになることを示す。まず，ｅは（Ｒ２）と（Ｒ３）を満たすからｅｓも（Ｒ２）と（Ｒ３）を満たし，ｓの定義より文字列ｅｓは（Ｒ１）と（Ｒ４）も満たすので，右ＭＵＭである。ゆえに，ｅｓは（Ｈ１）を満たす。
【００８０】
次に，文字列ｅが右ＭＵＭ  ｒを真のｐｒｅｆｉｘとして持つと仮定する。このとき，（Ｒ５）よりｒをｓｕｆｆｉｘとし，Ｐ（ｒ）＝Ｐ（ｍ）であるＭＵＭ  ｍが存在する。すると，Ｐ（ｅ）⊆Ｐ（ｒ）＝Ｐ（ｍ）よりｅはある入力文字列上でｍと左で重なり（Ａ４）に矛盾するか，ｍを真の部分文字列とするため（Ａ５）に矛盾し，こうしたｒは存在しないことがわかる。また，ｅｓが｜ｅ｜≦｜ｒ｜なる右ＭＵＭ  ｒを真のｐｒｅｆｉｘとして持つと仮定すると，ある文字ａについて｜ｅ｜≦｜ｒ｜≦｜ｒａ｜≦｜ｅｓ｜だから，Ｐ（ｅ）⊇Ｐ（ｒ）⊇Ｐ（ｒａ）⊇Ｐ（ｅｓ）であり，Ｐ（ｅｓ）＝Ｐ（ｅ）よりＰ（ｅ）＝Ｐ（ｒ）＝Ｐ（ｒａ）＝Ｐ（ｅｓ）である。これはｒが右ＭＵＭで（Ｒ４）を満たすことに矛盾するから，結局ｅｓの真のｐｒｅｆｉｘに右ＭＵＭは存在しないことがわかる。したがって，ｅｓは（Ｈ３）を満たす。
【００８１】
このｅｓが右ＵＥＢ−ｈｏｌｄｅｒでないと仮定する。このとき，ｅｓは（Ｈ１），（Ｈ３）を満足するから（Ｈ２）を満足しない。すなわち，ｅｓはＭＵＭでなく，かつ任意のＭＵＭ  ｍについて，文字列ｍｅｓを部分文字列とする入力文字列は存在しない。ｅｓがＭＵＭでないから，ある文字ａについて，Ｐ（ｅ）＝Ｐ（ａｅ）が成り立つ。このａｅが，（Ａ１）−Ａ５）満たすことを示す。
【００８２】
文字列ａｅは，Ｐ（ｅ）＝Ｐ（ａｅ）だから（Ａ１）を満たし，ｅをｓｕｆｆｉｘとして含むから（Ａ２）と（Ａ３）を満たす。
文字列ａｅがあるＭＵＭ  ｍと左で重なると仮定すれば，ｅは（Ａ４）よりｍと重ならないから，図１１に示すように空文字列でないある文字列ｔについてｍ＝ｔａと書くことができ，ｔａｅ＝ｍｅが少なくとも１つの入力文字列１１０１の部分文字列になる。ところで，Ｐ（ｅｓ）＝Ｐ（ｅ）だからｅは必ずｓを伴って入力文字列中に現れるので，ｍｅｓも入力文字列１１０１の部分文字列になるが，ｅｓは（Ｈ２ｂ）を満たさないから，このようなＭＵＭ  ｍは存在しないはずで，矛盾が生じる。したがって，ａｅは左ではＭＵＭと重ならない。
【００８３】
一方，ａｅがあるＭＵＭ  ｍと右で重なると仮定すると，ｅが（Ａ４）を満たすからｅとｍは重ならないため，図１２に示すようにｅはｍのｐｒｅｆｉｘである。Ｐ（ｍ）⊆Ｐ（ｅ）＝Ｐ（ｅｓ）より，少なくとも１つの入力文字列１２０１上にｍとｅｓが，この入力文字列上に１度しか出現しないｅをｐｒｅｆｉｘとして出現するため，ｍとｅｓは一方が他方のｐｒｅｆｉｘの関係にある。ところが，ｅｓが（Ｈ３）を満たすことをすでに述べたから，ｍはｅｓの真のｐｒｅｆｉｘでない。よってｅｓがｍのｐｒｅｆｉｘ。（Ｒ６）より，ＭＵＭのｐｒｅｆｉｘである右ＭＵＭは，ＭＵＭである。ゆえに，ｅｓはＭＵＭでなければならないが，ｅｓが（Ｈ２ａ）を満たさないことに矛盾する。したがって，ａｅもＭＵＭと右で重ならない。すなわち，ａｅは（Ａ４）を満たす。
【００８４】
さらに，ａｅの真の部分文字列でＭＵＭである文字列ｍが存在すると仮定する。ｅ＝ｍと仮定すると，ｓ＝εならばｍ＝ｅ＝ｅｓだからｅｓが（Ｈ２ａ）を満たさないことに矛盾し，ｓ≠εならば，ｍ＝ｅはｅｓの真のｐｒｅｆｉｘであり，ｍは右ＭＵＭだから，ｅｓが（Ｈ３）を満たすことに矛盾する。ゆえに，ｅ≠ｍ。さらに，ｅが（Ａ５）を満たすから，ｍはｅの部分文字列でもない。よって，図１３に示すように，ｍはａｅの真のｐｒｅｆｉｘである。したがって，ある文字列ｔ，ｔ’を用いてｍ＝ａｔ，ｅ＝ｔｔ’と書くことができる。ここで，ｍ＝ａならば，Ｐ（ａｅ）＝Ｐ（ｅ）＝Ｐ（ｅｓ）よりある入力文字列１３０１上にａｅｓ＝ｍｅｓが部分文字列として存在し，ｅｓが（Ｈ２ｂ）を満たさないことに矛盾するから，ｍ≠ａであり，ｔ≠εである。一方，ｔ’＝εならば，ｍ＝ａｔ＝ａｅよりｍはａｅの真の部分文字列でなくなるから，ｔ’≠ε。ところで，Ｐ（ｅ）＝Ｐ（ａｅ）よりａｅ＝ａｔｔ’＝ｍｔ’は少なくとも１つの入力文字列１３０１の部分文字列である。したがって，ｅ＝ｔｔ’はｍ＝ａｔと左で重なってしまうので（Ａ４）に矛盾するから，ａｅの真のｐｒｅｆｉｘでＭＵＭである文字列の存在は否定される。よって，ａｅの真の部分文字列にＭＵＭは存在しない。つまり，ａｅは（Ａ５）を満たす。
【００８５】
以上で，ａｅが（Ａ１）−（Ａ５）を満たすとわかった。ところが，ｅはａｅの真の部分文字列であり，ｅが（Ａ６）を満たすことに矛盾する。したがって，ｅｓが（Ｈ２）を満足しないとした仮定が誤りであることがわかる。すなわち，ｅｓは（Ｈ２）も満足し，右ＵＥＢ−ｈｏｌｄｅｒである。ゆえに，ｅは（Ｅ１）を満たす。
（Ｅ２）について：
文字列ｅは（Ａ２）を満たすから，明らかに（Ｅ２）を満たす。
（Ｅ３）について：
文字列ｅは（Ａ３）を満たすから，明らかに（Ｅ３）を満たす。
（Ｅ４）について：
文字列ｅは（Ａ４）を満たすから，明らかに（Ｅ４）を満たす。
（Ｅ５）について：
文字列ｅは（Ａ５）を満たすから，明らかに（Ｅ５）を満たす。
（Ｅ６）について：
ＵＥＢ  ｅをｐｒｅｆｉｘとして持ち，（Ｅ１）−（Ｅ５）を満たす文字列ｅ’の存在を仮定する。（Ａ１）−（Ａ５）は，（Ｅ１）−（Ｅ５）のみから導けたから，ｅ’は（Ａ１）−（Ａ５）を満たす。しかし，ｅは（Ａ６）を満たすから，このようなｅ’は存在しないはずである。よって，（Ｅ６）も満たされる。
【００８６】
以上で，条件（Ａ１）−（Ａ６）が条件（Ｅ１）−（Ｅ６）と等価であることを示した。したがって，本発明のＵＥＢ抽出方法で，条件（Ａ１）−（Ａ６）を満たす文字列すなわちＵＥＢを過不足無く抽出できることを示すには，（Ｅ１）−（Ｅ６）の条件を満たす文字列を過不足なく抽出できることを示せばよい。
【００８７】
まず，（ｅ１）−（ｅ３）の方法で，「ＵＥＢである」と印がついたノードｖのパスラベルの，長さＵＥＢｌｅｎｇｔｈ（ｖ）のｐｒｅｆｉｘ  ｅは，（Ｅ１）−（Ｅ６）を満たすことを示す。
（Ｅ１）について：
右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘである文字列だけを抽出するから，ｅは（Ｅ１）を満たす。（Ｅ２）について：
条件（ｅ３ｂ）より，ＵＥＢｌｅｎｇｔｈ（ｖ）がｕ以上の，「右ＵＥＢ−ｈｏｌｄｅｒである」と印があるノードｖだけにＵＥＢであるとの印をつけるから，ｅは（Ｅ２）を満たす。
（Ｅ３）について：
文字列ｅが（Ｅ３）を満たさないと仮定すると，ｅはある入力文字列ｉ上でｊ番目とｊ’番目に現れ，ｊ≠ｊ’である。すると，入力文字列ｉのｊ番目の文字とｊ’番目の文字から始まるｓｕｆｆｉｘのｐｒｅｆｉｘはｅだから，リーフ（ｉ，ｊ）とリーフ（ｉ，ｊ’）のパスラベルがいずれもｅをｐｒｅｆｉｘにもつ。ｅの長さはＵＥＢｌｅｎｇｔｈ（ｖ）だから，条件（ｅ３ａ）が満たされたことよりパスラベルのｐｒｅｆｉｘにｅを持つリーフへのポインタは，必ずｖを通る。しかし，ｈは右ＵＥＢ−ｈｏｌｄｅｒであり，どの入力文字列中にも高々１回しか現れないので，リーフ（ｉ，ｊ）とリーフ（ｉ，ｊ’）のうち，少なくともどちらか片方のリーフへのパスはｖを通ることができないから，矛盾を生じる。つまり，ｅが（Ｅ３）を満たさないと矛盾が生じるから，ｅは（Ｅ３）を満足しなければならないことがわかる。（Ｅ４），（Ｅ５）について：
ステップ（ｅ２ｂ）において，変数ｃの値７０３（図７参照）は，入力文字列ｉにおいてｊ番目の文字から始まる部分文字列で，入力文字列ｉにおいてｊ番目の文字以外には，任意のＭＵＭの先頭の文字と，任意のＭＵＭの終端の次の文字を含まない，最も長い文字列の長さとなっている。一方，任意の右ＵＥＢ−ｈｏｌｄｅｒ  ｈについて，ｐ（ｖ）＝ｈなるノードをｖとすると，ｈが入力文字列ｉのｊ番目の文字で始まるような全てのｉ，ｊについて，ステップ（ｅ２ｂ）でＵＥＢｌｅｎｇｔｈ（ｖ）はその時点のＵＥＢｌｅｎｇｔｈ（ｖ）と変数ｃの値７０３のうち，小さいほうの値に更新される。また，ＵＥＢｌｅｎｇｔｈ（ｖ）の初期値は，｜ｐ（ｖ）｜＝｜ｈ｜である。したがって，（ｅ２）が完了した時点で，ＵＥＢｌｅｎｇｔｈ（ｖ）は，次の条件（ｅ４ａ）および（ｅ４ｂ）を満足する最大の整数ｋとなる。
（ｅ４ａ）  ｋ≦｜ｈ｜
（ｅ４ｂ）  ｈの長さｋのｐｒｅｆｉｘで，ＭＵＭと重なる文字列や，ＭＵＭを部分文字列とする文字列は存在しない。
【００８８】
ゆえに，文字列ｅは（Ｅ４）と（Ｅ５）を満たす。
（Ｅ６）について：
ＵＥＢｌｅｎｇｔｈ（ｖ）は，ｅをｐｒｅｆｉｘとする右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘで，（Ｅ４）と（Ｅ５）を満たす最長のものの長さである。ｅの長さはＵＥＢｌｅｎｇｔｈ（ｖ）だから，（Ｅ６）も満たされる。
【００８９】
逆に，本発明の方法で「ＵＥＢである」と印がついたノードｖのＵＥＢｌｅｎｇｔｈ（ｖ）のｐｒｅｆｉｘ以外の文字列は，ＵＥＢでないことを示す。まず，右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘ以外の文字列はＵＥＢとみなされないが，（Ｅ１）よりこれらの文字列はＵＥＢでない。（ｅ３ａ）を満足しないために印がつかなかった右ＵＥＢ−ｈｏｌｄｅｒ  ｈのｐｒｅｆｉｘ  ｅについては，ｈの真のｐｒｅｆｉｘで，ｅをｐｒｅｆｉｘとして含む文字列ｓをパスラベルとするノードｗが存在する。このｓが，任意の入力文字列に高々１回しか現れないと仮定すると，ｓは（Ｒ３）を満たし，ｗのパスラベルだから（Ｒ１）を満たす。｜ｅ｜≧ｕのとき，｜ｓ｜≧｜ｅ｜≧ｕだからｓは（Ｒ２）を満たし，ｓｕｆｆｉｘ  ｔｒｅｅ  Ｔのノードのパスラベルだから（Ｒ４）を満たす。つまり，｜ｅ｜＜ｕ  でない限り，ｓは右ＭＵＭであり，ｈが右ＵＥＢ−ｈｏｌｄｅｒであることに矛盾。したがって，ｓは，少なくとも１つの入力文字列に２回以上出現する部分文字列である。ところが，ｅはｓのｐｒｅｆｉｘだから，ｅもこの入力文字列上に２回以上出現し，（Ｅ３）を満たさないからＵＥＢでない。｜ｅ｜＜ｕのときは，（Ｅ２）を満たさないから明らかにＵＥＢでない。結局，（ｅ３ａ）を満足しないために印がつかなかった右ＵＥＢ−ｈｏｌｄｅｒのｐｒｅｆｉｘ  ｅは，ＵＥＢでない。（ｅ３ｂ）を満足しないために印がつかなかった右ＵＥＢ−ｈｏｌｄｅｒ  ｈのｐｒｅｆｉｘ  ｅは，長さがｕ未満だから明らかに（Ｅ２）に反し，ＵＥＢでない。さらに，ＵＥＢｌｅｎｇｔｈ（ｖ）はｐ（ｖ）のｐｒｅｆｉｘで（Ｅ４）と（Ｅ５）を満たす最も長い文字列の長さだから，ｖのパスラベルのｐｒｅｆｉｘでＵＥＢｌｅｎｇｔｈ（ｖ）より長い文字列は（Ｅ４）または（Ｅ５）に矛盾し，ＵＥＢｌｅｎｇｔｈ（ｖ）より短い文字列は（Ｅ６）に矛盾する。
以上により，本発明の方法でＵＥＢであると判断されない文字列は，ＵＥＢではないことがわかった。
【００９０】
■本発明の方法の処理時間
本発明の方法の処理時間の，入力文字列の文字の総数Ｎに対する振る舞いについて検討する。本発明の処理は，Ｏ（Ｎ）の時間で完了できることが知られている（ｒ１）の方法と，入力文字列数や入力文字列の文字数に依存しない回数のｓｕｆｆｉｘ  ｔｒｅｅ  Ｔに対する深さ優先探査と，それぞれの深さ優先探査における各ノードに対する定数時間の処理と，全要素数がＮである３つの２次元配列Ｈｅａｄ，  Ｔａｉｌ，  Ｔｖの各要素に対する入力文字列数や入力文字列の文字数に依存しない回数の定数時間の処理により完了できる。ｓｕｆｆｉｘ  ｔｒｅｅに対する深さ優先探索は，１回あたりＯ（Ｎ）の時間で完了できる。したがって，本発明の方法全体の計算時間は，Ｏ（Ｎ）である。
【００９１】
■本発明の方法の効率的な実装方法
本発明の方法では，ｓｕｆｆｉｘ  ｔｒｅｅの深さ優先探査を繰り返し行なっているが，いくつかの処理でｓｕｆｆｉｘ  ｔｒｅｅの深さ優先探査の処理を統合することができる。（ｒ２）と（ｒ３），（ｍ１）と（ｍ３），（ｍ４）と（ｍ５），（ｍ６）と（ｍ７）は，変数を更新する順序に考慮しつつそれぞれ１回の深さ優先探査にまとめることができる。これにより，本発明の方法を実装することが容易になるとともに，実装されたシステムの性能向上も図ることができる。また，あるステップが終了した後には参照されない変数に割り当てられる記憶装置を，別の変数を記録するために再利用し，記憶装置の利用効率を向上させることができる。例えば，変数ｈ（ｖ），ｄ（ｖ），Ｃ（ｖ），ＵＥＢｌｅｎｇｔｈ（ｖ）は，同一の記憶領域を共有できる。また，変数Ｎ（ｖ）の値は，探査するノードｖのパスラベルの長さを再帰的に計算しつつステップ（ｍ７）を行なうこととすれば，記憶装置内にＮ（ｖ）の値を保持する必要はない。
【００９２】
■本発明の方法を実現する装置
本発明は，前記方法を実行するための装置も提供する。図８に，装置の構成の一例を示す。該装置は，主記憶８０６に上記方法を実行するプログラム８０５を格納し，さらにｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ  ８０８や入力文字列を格納する。プログラム８０５は，中央演算装置８０１により実行される。計算結果は，ディスプレイ８０２を通じて表示されるか，補助記憶装置８０７に格納されるか，またはそれら両方の処理が行なわれる。ユーザからの入力はキーボード８０３およびポインティングデバイス８０４を用いて行なわれる。
【００９３】
本発明の方法で得られたＵＥＢを表示する場合，見易さや解析の容易さの観点から，図１の例のように，ＵＥＢを入力文字列そのものまたは該入力文字列を象徴的に示す線分や矩形１０１上の，ＵＥＢである部分文字列に相当する位置１０２に，色を変えたり文字や記号で示すなど視覚的に見やすい方法で表示することが好ましい。また，入力文字列をそのものまたは該入力文字列を象徴的に示す線分や矩形１０１とともに表示するか否かに関わらず，ＵＥＢの入力文字列上の位置１０３を表示してもよい。また，同じ入力文字列に由来するＵＥＢを表示する際には，各ＵＥＢの開始位置の昇順とすることが好ましい。昇順の表示は，各入力文字列ｉについて変数ｊを，０から，入力文字列ｉの長さから１を減じた値まで増加させ，Ｔｖ［ｉ，ｊ］が「ＵＥＢである」と印がついたノードｖへのポインタであったとき，ｐ（ｖ）のｐｒｅｆｉｘで長さがＵＥＢｌｅｎｇｔｈ（ｖ）であるＵＥＢを表示することで，容易に実現できる。ＵＥＢを補助記憶装置８０７に格納する際にも，同じ入力文字列から得られたＵＥＢをともに格納する場合には，上記の表示方法で開始位置の昇順の表示を得たのと同様の方法で，ＵＥＢの開始位置の昇順を得てその順に格納することが好ましい。また，ＵＥＢを表示する場合には，複数の入力文字列に存在するＵＥＢが同一であるとわかるように，色や記号，文字，線１０４などを用いて判断できるように表示することが好ましい。また，補助記憶装置に８０７に記録する際も，複数のＵＥＢが同一であると識別可能なように番号あるいはＵＥＢごとに一意である数値または文字列を同時に記録することが好ましい。
【００９４】
■計算機実験による，本発明の方法のエクソン抽出能力の検証
本発明の方法を実装したシステムを作成し，本発明の方法で塩基配列のスプライシングパターンを解析できることを実証した。以下では，ｕの値を１５とした場合の結果について述べる。
【００９５】
はじめに，乱数を用いて，長さが３０文字の次の４つの塩基配列ｓ１，ｓ２，ｓ３，ｓ４を用意した。そして，これらを組み合わせ，長さが９０の４つの入力文字列ｓ１ｓ２ｓ３，ｓ１ｓ２ｓ４，ｓ１ｓ３ｓ４，ｓ２ｓ３ｓ４を作成し，本発明の方法を実装したソフトウェアを用いて，これらがｓ１，ｓ２，ｓ３，ｓ４の組み合わせであることを認識できるか試みた。パラメータｕの値は，１５とした。なお，ここで用いたｓ１，ｓ２，ｓ３，ｓ４は以下の配列である。
ｓ１＝  ＴＴＣＡＡＣＡＡＡＧＡＣＧＧＡＡＧＴＧＴＣＣＴＡＡＡＴＡＧＧ
ｓ２＝  ＧＴＧＣＴＧＡＣＡＧＴＧＣＴＧＴＴＡＧＡＡＣＴＡＣＡＧＧＣＴ
ｓ３＝  ＧＡＡＧＡＡＡＧＧＴＡＡＣＧＣＡＴＡＴＡＧＴＧＣＧＡＣＧＡＡ
ｓ４＝  ＧＧＴＧＧＣＡＴＧＣＣＡＴＧＧＡＣＧＣＡＴＡＣＴＣＣＧＴＡＡ
【００９６】
処理の結果，図１に示す４つのＵＥＢ（エクソン１，エクソン２，エクソン３，エクソン４）が得られた。この結果より，ｓ１は，エクソン１として抽出されたが，ｓ２，ｓ３，ｓ４はそれぞれ先頭の１塩基が欠けた配列として抽出された。この原因は，ｓ２，ｓ３，ｓ４がいずれもＧで始まるため，ｓ１およびｓ２の末尾にＧを加えた配列がＭＵＭとなり，ｓ２，ｓ３，ｓ４の先頭が１塩基削られた配列が右ＵＥＢ−ｈｏｌｄｅｒとなったためである。このように，末尾での配列の偶然の一致により，ＵＥＢは実際のエクソンより短くなる場合がありうる。しかし，完全に一致していないとはいえ，エクソン２，エクソン３，エクソン４はそれぞれｓ２，ｓ３，ｓ４にほぼ一致した。つまり，本発明の方法により，入力文字列が長さ３０塩基程度の４つの配列の組み合わせであると認識することができた。
【００９７】
次に，本発明の方法を実装したシステムを用いて，米国公共機関ＮＣＢＩの遺伝子データベースに登録されているスプライシングバリアント配列からＵＥＢを抽出し，得られたスプライシングパターンを該遺伝子データベースの記述と比較する実験を行なった。使用したのはヒトのウィルムス腫瘍遺伝子ＷＴ１の配列で，アクセッション番号がＮＭ＿００４９０６，  ＮＭ＿１５２８５７，  ＮＭ＿１５２８５８の３つの配列である。データベースには，ＮＭ＿１５２８５７の５７６番塩基以降とＮＭ＿１５２８５８の６７５番塩基以降の配列が選択的３’端配列であることと，ＮＭ＿１５２８５７に選択的５’端配列が存在することが記載されている。この３配列に対し，本発明の方法を実装したシステムを適用した結果は，図９の通りである。データベース記載されていたＮＭ＿１５２８５７，  ＮＭ＿１５２８５８の選択的３’配列は，開始位置を含めて正確にＵＥＢ５として認識された。さらに，ＮＭ＿１５２８５７の選択的５’端配列に関しては，データベースに位置の記述はなかったが，先頭から１１５番目の塩基までの配列が選択的５’端配列であり，ＮＭ＿００４９０６，  ＮＭ＿１５２８５８の先頭から２１３番目の塩基までの５’端配列に置き換わっていることがわかった。配列末尾のｐｏｌｙ−Ａ部分がＵＥＢ６として認識されたが，ＵＥＢがエクソンでなくｐｏｌｙ−Ａ配列であることは，ｐｏｌｙ−Ａ配列が入力配列の末尾にあること，配列中のアデニン（Ａ）の割合が極めて高いことから容易に判定できる。
【００９８】
なお，ウィルムス腫瘍遺伝子の配列について，本システムが認識したスプライシングパターンは，Ａｌｔｓｃｈｕｌ，  Ｓ．Ｆ．  ｅｔ  ａｌ．，  Ｎｕｃｌｅｉｃ  Ａｃｉｄ  Ｒｅｓｅａｒｃｈ，  ２５：３３８９−３４０２，  １９９７  の方法で，３つの配列の関係をペアワイズに比較した結果と，数塩基の差異を除き矛盾しないことを確認した。入力配列の総塩基数は５，５２９ｂｐで，計算時間はＣＰＵのクロック周波数が１．７ＧＨｚであるパーソナルコンピュータを用いて０．１秒程度であった。
【００９９】
■本発明の方法の，ｃＤＮＡ配列以外への適用
本発明は，ｍＲＮＡ配列のスプライシングパターン解析を目的としているが，比較ゲノム解析にも応用が可能である。入力文字列をｍＲＮＡ配列の代わりにゲノム配列とし，得られたＵＥＢがゲノム内の保存領域と解釈すれば，本発明の方法により，ゲノム配列の保存領域の位置と，複数のゲノム配列中の保存領域の対応関係が明らかにでき，比較ゲノム解析の有力な手段となる。
【０１００】
この他，文字列に使用される文字の種類が有限であれば，本発明の方法は塩基配列に依存せず一般の文字列を処理することができるため，アミノ酸配列のような塩基配列以外の配列や文字列に対しても，そのまま適用可能である。
【０１０１】
【発明の効果】
本発明によれば，ＥＳＴのような生体高分子配列から，エクソン配列が満たすべき条件を用いて構築されたエクソン配列のモデルで定義された配列を，与えられた配列長の総和の線形時間で抽出することができる。
【図面の簡単な説明】
【図１】４つのエクソンの組み合わせになっている４つの入力配列を，本発明の方法により解析した結果を表示した例を示す図。
【図２】ゲノム上の遺伝子の，発現およびスプライシングの説明図。
【図３】入力文字列，右ＭＵＭ，ＭＵＭ，右ＵＥＢ−ｈｏｌｄｅｒ，ＵＥＢの説明図。
【図４】Ｓｕｆｆｉｘ  ｔｒｅｅの説明図。
【図５】本発明の方法における，処理全体のフローチャート。
【図６】ＭＵＭの総数がＮのオーダー，それぞれのＭＵＭの出現回数の総和がＮの３／２乗のオーダーとなる入力文字列集合の，ｎ＝５の例を示す図。
【図７】図５中，ステップＳ５０５の右ＵＥＢ−ｈｏｌｄｅｒ抽出，および，ステップＳ５０６のＵＥＢ抽出方法の説明図。
【図８】本発明の方法を実現する装置の一例の説明図。
【図９】本発明の方法により，ウィルムス腫瘍遺伝子のスプライシングバリアントからエクソン配列を抽出した結果を表示した例を示す図。
【図１０】条件（Ｅ１）−（Ｅ６）より条件（Ａ６）が導かれることの説明において検討する文字列ｅ，ｅ’，ｓ，ｓ’，ｈ，ｍ’の関係を説明する図。
【図１１】条件（Ａ１）−（Ａ６）より条件（Ｅ１）が導かれることの説明において，ａｅと左で重なるＭＵＭが存在しないことを説明するために定義された文字列ｍ，ｔと，ａ，ｅ，ｓの関係を表した図。
【図１２】条件（Ａ１）−（Ａ６）より条件（Ｅ１）が導かれることの説明において，ａｅと右で重なるＭＵＭが存在しないことを説明するために定義された文字列ｍと，ａ，ｅ，ｓの関係を表した図。
【図１３】条件（Ａ１）−（Ａ６）より条件（Ｅ１）が導かれることの説明において，ａｅの真の部分文字列であるＭＵＭが存在しないことを説明するために定義された文字列ｍ，ｔ，ｔ’と，ａ，ｅの関係を表した図。
【図１４】条件（Ｅ１）−（Ｅ３）を満足する文字列ｅが（Ｅ７）を満足することの説明において，ｅ，ｓ，ｓ’，ｓ’’，ａ，ａ’，ｈ，ｈ’の関係を表した図。なお，ｈ’のうち，入力文字列１４０１上にあるのは，ｅｓに一致するｐｒｅｆｉｘの部分だけである。
【図１５】文字列ｓ，ｓ’が重なることの定義を説明する図。
【符号の説明】
１０１：  入力文字列を象徴的に示す矩形
１０２：  １０１上で，ＵＥＢである部分文字列に相当する位置
１０３：  ＵＥＢの入力文字列上の位置
１０４：  複数の入力文字列上にあるＵＥＢが同一であることを象徴的に示す線
２０１：  ゲノムＤＮＡ
２０２：  ゲノム上の遺伝子
２０３：  ｍＲＮＡ前駆体
２０４：  スプライシングの過程を象徴的に表す矢印
２０５：  イントロン
２０６：  エクソン
２０７：  ｍＲＮＡ
２０８：  ２０７でスプライシングの過程で除去されずに残ったエクソンの１つ２０９：  ｍＲＮＡ  ２０７  のスプライシングバリアントの１つ
２１０：  ｍＲＮＡ  ２０７で除去されたが，ｍＲＮＡ  ２０９で残ったエクソン
３０１：  入力文字列の例
３０２：  ３０１の入力文字列集合に対する右ＭＵＭを列挙したもの
３０３：  ３０１の入力文字列集合に対するＭＵＭを列挙したもの
３０４：  ３０１の入力文字列集合に対する右ＵＥＢ−ｈｏｌｄｅｒを列挙したもの
３０５：  ３０１の入力文字列集合に対するＵＥＢを列挙したもの
４０１：  文字列ＡＴＡＴＧとＴＴＡＧＴＡから構築されたｓｕｆｆｉｘ  ｔｒｅｅ
４０２：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のルートノード
４０３：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のリーフの１つ（「ｉ，  ｊ」と書かれているリーフは，文字列ｉのｊ番目から始まるｓｕｆｆｉｘに対応）
４０４：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のエッジの１つ
４０５：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のエッジのラベルの１つ
４０６：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のエッジの空文字列であるラベル
４０７：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のノードの１つ
４０８：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のルートノード４０２からノード４０７にいたるパス
４０９：  Ｓｕｆｆｉｘ  ｔｒｅｅ  ４０１のｓｕｆｆｉｘ  ｌｉｎｋの１つ
６０１：  ＭＵＭの総数がＮのオーダー，それぞれのＭＵＭの出現回数の総和がＮの３／２乗のオーダーとなる入力文字列集合の，ｎ＝５の例
６０２：  入力配列集合６０１のＭＵＭの１つ（ｔ（３，１））
７０１：  ２次元配列Ｈｅａｄの，入力文字列３についての要素を取り出したもの
７０２：  ２次元配列Ｔａｉｌの，入力文字列３についての要素を取り出したもの
７０３：  ＵＥＢ抽出方法において用いられる変数ｃのステップ（ｅ２ｂ）での値
８０１：  本発明の装置の中央演算装置
８０２：  本発明の装置のディスプレイ
８０３：  本発明の装置のキーボード
８０４：  本発明の装置のポインティングデバイス
８０５：  本発明の方法を実行するためのプログラム
８０６：  本発明の装置の主記憶装置
８０７：  本発明の装置の補助記憶装置
８０８：  本発明の装置の主記憶装置に記録されたｓｕｆｆｉｘ  ｔｒｅｅ  Ｔ
１００１：  ある入力文字列を象徴的に表す線分
１１０１：  ある入力文字列を象徴的に表す線分
１２０１：  ある入力文字列を象徴的に表す線分
１３０１：  ある入力文字列を象徴的に表す線分
１４０１：  ある入力文字列を象徴的に表す線分
１５０１：  ある入力文字列を象徴的に表す線分
【図１】
2004152023.tif 000005
【図２】
2004152023.tif 000006
【図３】
2004152023.tif 000007
【図４】
2004152023.tif 000008
【図５】
2004152023.tif 000009
【図６】
2004152023.tif 000010
【図７】
2004152023.tif 000011
【図８】
2004152023.tif 000012
【図９】
2004152023.tif 000013
【図１０】
2004152023.tif 000014
【図１１】
2004152023.tif 000015
【図１２】
2004152023.tif 000016
【図１３】
2004152023.tif 000017
【図１４】
2004152023.tif 000018
【図１５】
2004152023.tif 000019