アセンブリング前処理装置、該プログラム、及びコンピュータクラスタシステムの該制御方法
【課題】生物配列断片のインデックス作成処理の高速化を図るアセンブリング前処理装置を提供する。
【解決手段】生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する取得部と、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する担当判定部と、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報における部分配列情報の位置を示す位置情報を配列位置格納部に登録する登録部と、を備えるアセンブリング前処理装置により、上記課題の解決を図る。
【解決手段】生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する取得部と、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する担当判定部と、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報における部分配列情報の位置を示す位置情報を配列位置格納部に登録する登録部と、を備えるアセンブリング前処理装置により、上記課題の解決を図る。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態の一側面は、配列アセンブリングの前処理技術に関する。
【背景技術】
【０００２】
配列アセンブリングとは、バイオインフォマティクスにおいて短い塩基配列の断片から元の長い塩基配列を再構築することをいう。配列アセンブリングの１つに、De novo アセンブル（assemble）がある。De novo アセンブリとは、シーケンサ装置が出力したDNA（デオキシリボ核酸）、RNA（リボ核酸）等の生物配列（以下、「Read配列」と称する）を繋ぎ合わせて（assemble）、元の生物配列を再構築することをいう。ここで、シーケンサ装置とは、DNA/ RNA等の塩基配列を自動的に読み取る装置である。
【０００３】
アセンブル手法として、例えば、De Bruijn Graphによるアセンブルがある。De Bruijn Graphによるアセンブルでは、まず、Read配列をある長さの断片に細切れにした配列（生物配列断片）を生成する。以下では、生物配列断片を、「K-mer」と称する。次に、K-merからDe Bruijn Graphを作成する。そして、このDe Bruijn Graphについて、オイラーパス問題を解く（すなわち、De Bruijn Graphの全辺を通るパスを求める）。
【０００４】
De Bruijn Graphを作成する前処理として、K-merがRead配列のどこに存在するのかを管理するK-merインデックステーブルが作成されるが、正確なアセンブル処理を行うには、大量のRead配列を用いる。したがって、コンピュータを用いて、De Bruijn Graphを作成する場合、その前処理に用いるK-merインデックステーブルの作成に、大量のメモリ容量が消費される。
【０００５】
ところで、大量のデータを複数のサーバを用いて処理する技術の１つに、分散KVS（キーバリュー型データストア ： Key-Value Store）がある。分散KVSとは、キーと値からなる比較的単純な構造の連想配列を、多数のサーバで高速に処理するデータストアを示す。分散KVSでは、KVSクライアント装置が、キーの値に応じて、保存先のサーバ装置（KVSサーバ）を変えることで、複数のサーバに分散してデータを保存する。これにより、分散KVSでは、大量のデータをスケールアウト型で扱うことができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Daniel R. Zerbino and Ewan Birney “Velvet: Algorithms for de novo short read assembly using de Bruijn graph”, Genome Res., 2008 18: 821-829
【非特許文献２】“MEMCACHED”、[online] 、［平成23年11月15日検索］、インターネット、<http://memcached.org/>
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように、コンピュータを用いて、De Bruijn Graphを作成する場合、その前処理に用いるK-merインデックステーブルの作成に際して、例えば、数十〜数百ギガバイトのオーダで大量のメモリ容量が消費される。したがって、そのような膨大なデータを処理するために、処理時間が長くなる。
【０００８】
また、分散KVSを用いて、複数のKVSサーバにK-merインデックステーブルの作成を実行させる場合でも、KVSクライアントにそれらのKVSサーバに処理を分散させる処理が集中する。そのため、KVSクライアントでの分散処理がボトルネックとなり、処理の高速化を図ることができない可能性がある。
【０００９】
そこで、本実施形態の一側面によれば、生物配列断片のインデックス作成処理の高速化を図る情報処理装置を提供する。
【課題を解決するための手段】
【００１０】
本実施形態の一側面にかかるアセンブリング前処理装置は、取得部、担当判定部、登録部を含む。取得部は、生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する。担当判定部は、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する。登録部は、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報における部分配列情報の位置を示す位置情報を配列位置格納部に登録する。
【発明の効果】
【００１１】
本実施形態の一側面によれば、生物配列断片のインデックス作成処理の高速化を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】K-merインデックステーブルを説明するための図である。
【図２】K-merインデックステーブルの作成を説明するための図（その１）である。
【図３】K-merインデックステーブルの作成を説明するための図（その２）である。
【図４】本実施形態におけるアセンブリング前処理装置の構造の一例を示す。
【図５】本実施形態における複数のプロセスによる並列処理を実現する方法の一例を示す。
【図６】本実施形態におけるK-merインデックス作成処理の全体のフローを示す。
【図７】本実施形態の一実施例におけるアセンブリング前処理システムの一例を示す。
【図８】本実施形態の一実施例におけるK-merインデックス部分テーブル及びK-merインデックステーブルのデータ構造を示す。
【図９】本実施形態の一実施例における並列化された各プロセス（各計算機）が行うK-merインデックス部分テーブル作成処理フローを示す。
【図１０】本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。
【発明を実施するための形態】
【００１３】
図１は、K-merインデックステーブルを説明するための図である。図１の例では、Read配列は、上段より、Read配列０、Read配列１、Read配列３、Read配列４、・・・で示される。Read配列は、位置０〜位置２７までの２８個の塩基配列で表される。ここで、「A」はアデニンを示す。「G」はグアニンを示す。「T」は、チミンを示す。「C」は、シトシンを示す。
【００１４】
K-mer n（n=0，1，2，・・・）は、Read配列を1文字ずらしで長さKの文字列に区切った部分配列である。例えば、K-mer0は、Read配列０の位置０から６文字切り取った部分配列である。K-mer1は、Read配列０の位置１から６文字切り取った部分配列である。K-mer2は、Read配列０の位置２から６文字切り取った部分配列である。
【００１５】
このように、i番目のRead配列およびそのRead配列のｊ番目の位置によって、K-merがどのRead配列のどの場所に存在するかを特定することができる。このように、各K-merがどのRead配列のどの場所に存在するかの情報を保持するテーブルが、K-merインデックステーブルである。
【００１６】
図２及び図３は、K-merインデックステーブルの作成を説明するための図である。コンピュータを用いて、K-merインデックステーブルを作成する場合について考える。この場合、CPU（Central Processing Unit）は、Read配列を読み込むと、図２に示すように、Read配列の先頭から順次K-merを取得する。CPUは、順次取得したK-merをキーとし、K-merの位置情報（Read:i、Position:j）を値として、連想配列格納部に格納していく。ここで、位置情報（Read:i、Position:j）は、i番目のRead配列、およびそのRead配列のｊ番目の位置を示す。また、連想配列格納部はコンピュータ上のメモリに配置される。
【００１７】
例えば、K-mer0の場合、キーとして「ACGTGT」が格納され、値として「Read:0、Position:0」が格納される。例えば、K-mer1の場合、キーとして「CGTGTT」が格納され、値として「Read:0、Position:1」が格納される。例えば、K-mer2の場合、キーとして「GTGTTC」が格納され、値として「Read:0、Position:2」が格納される。
【００１８】
図３に示すように、Read配列から取得したK-mer（対象K-mer）と同一のK-mer（基準K-mer）が連想配列格納部に既に存在していた場合、CPUはK-merインデックステーブルに、基準K-merの位置情報と対象K-merの位置情報を関係付けて登録する。
【００１９】
例えば、「Read:0、Position:15」にあるK-mer「CGTGTT」を連想配列格納部に格納する場合について考える。この場合、K-mer「CGTGTT」は既に連想配列格納部に登録されているので、「Read:0, Position: 15」のK-merが「Read:0, Position: 1」のK-merと同一であることを示す情報をK-merインデックステーブルに登録する。
【００２０】
このようにして、連想配列格納部及びK-merインデックステーブルが作成される。
ところが、Read配列が大量に存在する場合、K-merも大量になり、大量のK-merを処理することになる。その結果、連想配列格納部が肥大化し、コンピュータ上のメモリを大量に消費することになる。また、コンピュータの処理量も増加するので、処理時間が長くなる可能性もある。
【００２１】
そこで、処理時間を短縮させるために、CPUの処理効率を向上させることが考えられる。例えば、複数のスレッドが同時に動作するマルチスレッド方式を用いた場合には、各スレッドが、自身が担当するRead配列について処理を行う。
【００２２】
しかしながら、マルチスレッド方式の場合、各スレッドは、同一プロセス内で動作しているため、メモリ空間を共有している。したがって、複数のスレッドは、共有メモリ上にある同一の連想配列格納部を更新することになる。そのため、例えば、連想配列格納部において、同じキーを有するエントリを更新する場合にはスレッド間の競合が生じるので、排他制御を行う。排他制御とは、あるスレッドに資源を独占的に利用させている間は、他のスレッドが利用できないようにする事で整合性を保つ処理をいう。
【００２３】
排他制御の結果、あるスレッドが資源を利用している間は、競合する他のスレッドはその利用が終了するまで待つことになり、待ち時間が発生する。そのため、処理時間が遅延する。
【００２４】
また、複数のスレッドを用いて処理をしても、各スレッドはプロセスメモリ空間を共有するため、プロセスメモリ空間を分離できない。したがって、プロセス当たりのメモリ使用量は変わらない。
【００２５】
そこで、プロセス当たりの処理量を軽減させる方法の１つとして、分散KVSを利用することが考えられる。しかしながら、分散KVSを用いて、複数のKVSサーバにK-merインデックステーブルの作成を実行させる場合でも、KVSクライアントにそれらのKVSサーバに処理を分散させる処理が集中する。そのため、KVSクライアントがボトルネックとなり、処理の高速化を図ることができない可能性がある。
【００２６】
そこで、本実施形態では、以下に説明するように、生物配列断片のインデックス作成処理の高速化を図る情報処理装置を提供する。
【００２７】
図４は、本実施形態におけるアセンブリング前処理装置の構造の一例を示す。アセンブリング前処理装置１０は、複数存在する。アセンブリング前処理装置１０は、取得部１１、担当判定部１２、登録部１５を含む。
【００２８】
取得部１１は、生物配列情報２１の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報（K-mer）を１文字ずつずらして取得する。取得部１１の一例として、図９のＳ１３、Ｓ１４の処理がある。生物配列情報２１は、シーケンサ装置が出力したDNA/ RNA等の生物配列（Read配列）である。
【００２９】
担当判定部１２は、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する。担当判定部１２の一例として、図９のＳ１５〜Ｓ１７の処理がある。
【００３０】
登録部１５は、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報２１における部分配列情報の位置を示す位置情報を配列位置格納部２０に登録する。登録部１５の一例として、図９のＳ１８、Ｓ２０の処理がある。
【００３１】
このように構成することにより、各プロセスは、自身の担当するK-merを対象にしてK-merインデックステーブルを作成することができるので、プロセス当たりの処理量が減少すると共に、処理の並列化を図ることができる。したがって、生物配列断片のインデックス作成処理の高速化を図ることができる。
【００３２】
担当判定部１２は、算出部１３、剰余判定部１４を含む。
算出部１３は、部分配列情報のハッシュ値を算出し、ハッシュ値を第１の値で割ったときの剰余値を算出する。第１の値は、アセンブリング前処理装置の数、またはプロセス数を示す。ここでのプロセスとは、取得部１１、算出部１２、剰余判定部１３、部分配列判定部１４、及び登録部１５により実行される一連の処理を実行するプロセスを示す。算出部１３の一例として、図９のＳ１５、Ｓ１６の処理がある。
【００３３】
剰余判定部１４は、算出した剰余値が、第２の値であるか否かを判定する。剰余判定部１４の一例として、図９のＳ１７の処理がある。
【００３４】
このように構成することにより、K-merにより一意に処理を担当するプロセスが決定され、同一のK-merは、同一のプロセスにより処理することができる。
【００３５】
登録部１５は、部分配列判定部１６を含む。部分配列判定部１６は、算出した剰余値が第２の値であると判定された場合、取得した部分配列情報が、部分配列をキーとする連想配列を格納する連想配列格納部１８に登録されているか否かを判定する。部分配列判定部１６の一例として、図９のＳ１８の処理がある。連想配列格納部１８の一例として、連想配列格納部４３がある。
【００３６】
このように構成することにより、K-merインデックステーブル作成のために用いる連想配列を作成することができる。また、プロセス単位で連想配列格納部へK-merを登録することができるので、マルチスレッド方式を採用した場合の競合の問題も生じない。
【００３７】
登録部１５は、配列位置登録部１７を含む。配列位置登録部１７は、部分配列情報が連想配列格納部１８に登録されている場合、生物配列情報における部分配列情報の位置情報と、連想配列格納部に登録されている部分配列情報の生物配列情報２１における位置情報とを関係付けて配列位置格納部２０に登録する。配列位置登録部１７の一例として、Ｓ１９の処理がある。配列位置格納部２０の一例として、例えば、K-merインデックステーブル５６がある。
【００３８】
このように構成することにより、K-merインデックステーブルを作成することができる。
【００３９】
図５は、本実施形態における複数のプロセスによる並列処理を実現する方法の一例を示す。各プロセスは、ハッシュ関数を用いて、生体配列から読み出したK-merのハッシュ値を算出する。各プロセスは、そのハッシュ値をプロセス数で割った剰余に応じて、自身がそのK-merについてのK-merインデックステーブル作成処理を担当するか否かを判定する。そのプロセスがそのK-merについてのK-merインデックステーブル作成処理を担当すると判定した場合、そのプロセスは、そのK-merについてのK-merインデックステーブル作成処理を行う。これにより、K-merのハッシュ値をプロセス数で割った剰余に応じて、K-merについてのK-merインデックステーブル作成処理を担当するプロセスを動作させることができる。
【００４０】
例えば、図５に示すように、K-merインデックステーブル作成処理を４つのプロセスで行うとする。K-merインデックステーブル作成処理では、各プロセスは、自身が担当するK-merであると判定した場合、そのK-merが連想配列格納部に登録されていなければ、そのK-merを連想配列格納部に登録する。
【００４１】
各プロセスは、自身が担当するK-merであると判定した場合、そのK-merが連想配列格納部に登録されていれば、次の処理を行う。すなわち、そのプロセスは、K-merインデックステーブルにK-merの位置情報と、連想配列格納部２１に登録されているK-merの位置情報を関係付けて登録する。
【００４２】
なお、各プロセスは、自身の担当するK-merを判別するために、予め固有の値（担当No.）を保持している。例えば、図５の場合、プロセス０は、値０を有している。プロセス１は、値１を有している。プロセス２は、値２を有している。プロセス３は、値３を有している。K-merのハッシュ値をプロセス数で割った剰余が、各プロセスが予め有している値と同じであれば、そのプロセスがそのK-merについてのK-merインデックステーブル作成処理を担当する。
【００４３】
例えば、図５において、各プロセスは、Read配列からK-mer nを読み出し、ハッシュ関数を用いてK-mer nのハッシュ値を計算し、計算したハッシュ値を４で割った場合の剰余を計算する。剰余が０である場合、プロセス０がそのK-mer nについてのK-merインデックステーブル作成を担当する。
【００４４】
担当プロセスを決定するときの指標は、K-merのハッシュ値をプロセス数で割って得られる剰余以外でも、次の条件を満たせばよい。その条件とは、（１）K-merにより一意の値が決まる、（２）担当プロセスが少なくとも１つ存在する、（３）K-merがノード毎に十分に分散（一様分布に近ければ近いほどよい）である。
【００４５】
図６は、本実施形態におけるK-merインデックス作成処理の全体のフローを示す。上述の通り、各プロセスは、予め担当No.を有している。例えば、図６の場合、プロセス０（３１−０）は、担当No.として値０を有している。プロセス１（３１−１）は、担当No.として値１を有している。プロセス２（３１−２）は、担当No.として値２を有している。プロセス３（３１−３）は、担当No.として値３を有している。
【００４６】
各プロセス０〜３（３１−０〜３１−３）は、Read配列３０を読み込み、K-merインデックス部分テーブル作成処理Ｓ１（Ｓ１−０〜Ｓ１−３）を行う。ここで、K-merインデックス部分テーブル作成処理Ｓ１とは、次の処理をいう。すなわち、各プロセスは、Read配列３０から読み出したK-merのハッシュ値をハッシュ関数を用いて算出する。そのハッシュ値をプロセス数で割った剰余に応じて、そのプロセスが、自身が担当するK-merについての処理であるかを判定する。そのプロセスが担当するK-merについての処理であると判定した場合、そのプロセスは、そのK-merが連想配列格納部に登録されていなければ、そのK-merを連想配列格納部に登録する。そのK-merが連想配列格納部に登録されていなければ、そのプロセスは、次の処理を行う。すなわち、そのプロセスは、K-merインデックス部分テーブル３２（３２−０〜３２−３）にK-merの位置情報と、連想配列格納部に登録されているK-merの位置情報を関係付けて登録する。
【００４７】
各プロセス０〜３において、K-merインデックス部分テーブル作成処理Ｓ１（Ｓ１−０〜Ｓ１−３）の終了後、特定のプロセスは、次の処理を行う。すなわち、特定のプロセスは、各プロセスで作成されたK-merインデックス部分テーブルを連結して、K-merインデックステーブル３３を作成する（コンカーチネート処理Ｓ２）。なお、特定のプロセスは、プロセス０〜３のいずれかでもよいし、プロセス０〜３とは別のプロセスでもよい。
【００４８】
図７は、本実施形態の一実施例におけるアセンブリング前処理システムの一例を示す。アセンブリング前処理システムは、計算機４０（４０−０〜４０−３）及びストレージ装置５０を含む。計算機４０（４０−０〜４０−３）及びストレージ装置５０は、ネットワーク５７で接続されている。
【００４９】
計算機４０は、ＣＰＵ４１（４１−０〜４１−３）、メモリ４２（４２−０〜４２−３）を含む。ＣＰＵ４１は、計算機全体の動作を制御する。メモリ４２は、データを格納する記憶装置である。メモリ４２（４２−０〜４２−３）は、連想配列格納部４３（４３−０〜４３−３）を保持する。
【００５０】
計算機４０−０のメモリ４２−０は、さらに、担当管理テーブル４４を保持する。担当管理テーブル４４は、担当No.と、各計算機４０−０を識別する計算機識別情報とが関係付けられて格納されている。なお、担当管理テーブル４４のエントリをカウントすれば、プロセス数を得ることができる。
【００５１】
ストレージ装置５０は、ＣＰＵ５１、メモリ５２、共有ディスク５３を含む。ＣＰＵ５１は、ストレージ装置５０全体の動作を制御する。メモリ５２は、データを格納する記憶装置である。共有ディスク５３は、ネットワーク５７を介して、計算機４０−０〜４０−３が共有で利用する大容量記憶装置である。共有ディスク５３は、Read配列５４、K-merインデックス部分テーブル５５、K-merインデックステーブル５６を格納する。
【００５２】
図８は、本実施形態の一実施例におけるK-merインデックス部分テーブル及びK-merインデックステーブルのデータ構造を示す。K-merインデックス部分テーブル５５及びK-merインデックステーブル５６のデータ構造は同一であるので、以下では、K-merインデックス部分テーブル５５について説明する。
【００５３】
K-merインデックス部分テーブル５５は、「基準K-merのRead配列の番号」６１、「基準K-merのRead配列における位置」６２、「対象K-merのRead配列の番号」６３、「対象K-merのRead配列における位置」６４を含む。
【００５４】
ここで、基準K-merとは、連想配列格納部４３（４３−０〜４３−３）に格納されているK-merをいう。具体的には、基準K-merは、各プロセス（計算機４０）において処理を実行する場合に、各プロセス（計算機４０）でRead配列から１文字ずつずらして読み出して得られた同一のK-merのうち、最初に検出されたK-merのことである。
【００５５】
対象K-merとは、各プロセス（計算機４０）でRead配列から１文字ずつずらして読み出して得られた同一のK-merのうち、２番目以降に検出されたK-merのことである。
【００５６】
「基準K-merのRead配列の番号」６１及び「基準K-merのRead配列における位置」６２には、連想配列格納部４３（４３−０〜４３−３）に格納されているK-mer（基準K-mer）のRead配列の番号、及びそのRead配列における位置が格納される。
【００５７】
「対象K-merのRead配列の番号」６３、及び「対象K-merのRead配列における位置」６４は、基準K-merの検出後に検出された、基準K-merと同一のK-mer（対象K-mer）のRead配列の番号、及びそのRead配列における位置が格納される。
【００５８】
図９は、本実施形態の一実施例における並列化された各プロセス（各計算機）が行うK-merインデックス部分テーブル作成処理フローを示す。ＣＰＵ４１は、担当No.とプロセス数Ｐを取得する（Ｓ１１）。本実施形態では、ＣＰＵ４１−１〜４１−３は、計算機４０−０にアクセスして、自身の計算機識別番号をキーとして担当管理テーブル４４から自身の担当No.を取得し、担当管理テーブル４４のエントリをカウントしてプロセス数Pを取得する。計算機４０−０については、ＣＰＵ４１−０は、メモリ４２−０にアクセスし、自身の計算機識別番号をキーとして担当管理テーブル４４から自身の担当No.を取得し、担当管理テーブル４４のエントリをカウントしてプロセス数Pを取得する。ＣＰＵ４１−０は、担当No.として値０を取得する。ＣＰＵ４１−１は、担当No.として値１を取得する。ＣＰＵ４１−２は、担当No.として値２を取得する。ＣＰＵ４１−３は、担当No.として値３を取得する。なお、担当No.とプロセス数Ｐは、各計算機４０に予め設定しておいてもよい。なお、プロセス数Ｐは、本実施例では、４である。
【００５９】
ＣＰＵ４１は、初期化処理を行う（Ｓ１２）。すなわち、ＣＰＵ４１は、変数ｉ=０、ｊ＝０を設定すると共に、空の連想配列格納部４３を作成する。
【００６０】
ＣＰＵ４１は、ストレージ装置５０の共有ディスク５３にアクセスし、ｉ番目のRead配列５４を読み込む（Ｓ１３）。それから、ＣＰＵ４１は、そのｉ番目のRead配列におけるｊ番目のK-merを取得する（Ｓ１４）。
【００６１】
ＣＰＵ４１は、予めメモリ４２に展開したハッシュ関数を用いて、取得したK-merのハッシュ値Ｈを算出する（Ｓ１５）。ＣＰＵ４１は、算出したハッシュ値Ｈをプロセス数Ｐで割って得られる剰余を算出する（Ｓ１６）。
【００６２】
ＣＰＵ４１は、得られた剰余が、担当No.と等しいか否かを判定する（Ｓ１７）。得られた剰余が担当No.と等しくない場合（Ｓ１７で「Ｎｏ」）、Ｓ２１の処理に進む。得られた剰余が担当No.と等しい場合（Ｓ１７で「Ｙｅｓ」）、ＣＰＵ４１は、その取得したK-merが連想配列格納部４３に登録されているか否かを判定する（Ｓ１８）。
【００６３】
その取得したK-merが連想配列格納部４３に登録されていない場合（Ｓ１８で「Ｎｏ」）、ＣＰＵ４１は、その取得したK-mer（基準K-mer）の位置（ｉ，ｊ）を、連想配列格納部４３に登録する（Ｓ１９）。
【００６４】
その取得したK-merが連想配列格納部４３に登録されている場合（Ｓ１８で「Ｙｅｓ」）、ＣＰＵ４１は、次の処理を行う。ＣＰＵ４１は、取得したK-mer（対象K-mer）の位置（ｉ，ｊ）と、連想配列格納部４３に登録されているK-mer（基準K-mer）の位置とを関係付けて、ストレージ装置５０の共有ディスク５３内のK-merインデックス部分テーブル５５に登録する（Ｓ２０）。K-merインデックス部分テーブル５５は、ストレージ装置５０の共有ディスク５３内に計算機４０毎に構築される。
【００６５】
Ｓ１７で「Ｎｏ」の場合、またはＳ２０もしくはＳ２１の終了後、ＣＰＵ４１は、変数ｊをインクリメントする（Ｓ２１）。ＣＰＵ４１は、そのｉ番目のRead配列におけるｊ番目のK-merが存在するか否かを判定する（Ｓ２２）。
【００６６】
そのｉ番目のRead配列におけるｊ番目のK-merが存在する場合（Ｓ２２で「Ｙｅｓ」）、Ｓ１４の処理へ戻る。そのｉ番目のRead配列におけるｊ番目のK-merが存在しない場合（Ｓ２２で「Ｎｏ」）、ＣＰＵ４１は、変数ｉをインクリメントする（Ｓ２３）。
【００６７】
ＣＰＵ４１は、ｉ番目のRead配列が存在するか否かを判定する（Ｓ２４）。ｉ番目のRead配列が存在する場合（Ｓ２４で「Ｙｅｓ」）、Ｓ１４の処理へ戻る。ｉ番目のRead配列が存在しない場合（Ｓ２４で「Ｎｏ」）、本フローは終了する。
【００６８】
これにより、各プロセス（各計算機４０）で作成されたK-merインデックス部分テーブル５５が、ストレージ装置５０の共有ディスク５３内に格納される。
【００６９】
計算機４０−０は、ストレージ装置５０の共有ディスク５３内にある各プロセス（各計算機４０）で作成されたK-merインデックス部分テーブル５５を連結して、K-merインデックステーブル５６を作成し、共有ディスク５３に格納する。
【００７０】
なお、Ｓ２０において、ＣＰＵ４１は、対象K-merの位置と、基準K-merの位置とを関係付けて、ストレージ装置５０の共有ディスク５３内の、対応するK-merインデックス部分テーブル５５に登録したが、これに限定されない。例えば、各ＣＰＵ４１は、対象K-merの位置と、基準K-merの位置とを関係付けて、ストレージ装置５０の共有ディスク５３内の、共有のK-merインデックステーブル５５に登録するようにしてもよい。この場合、K-merインデックステーブル５５を管理するDBMS（DataBase Management System）によって、K-merインデックステーブル５５に対する各計算機４０からのエントリの追加処理が制御される。
【００７１】
図１０は、本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。コンピュータ７０は、本実施形態の処理を行うプログラムを読み込むことにより、アセンブリング前処理装置１０、または計算機４０として機能する。
【００７２】
コンピュータ７０は、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８、バス７９を含む。コンピュータ７０は、出力機器８１、及び入力機器８２と接続可能である。
【００７３】
ここで、ＣＰＵは、中央演算装置を示す。ＲＯＭは、リードオンリメモリを示す。ＲＡＭは、ランダムアクセスメモリを示す。Ｉ／Ｆは、インターフェースを示す。バス７９には、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８が接続されている。読み取り装置７８は、可搬型記録媒体を読み出す装置である。出力機器８１は、出力Ｉ／Ｆ７１に接続されている。入力機器８２は、入力Ｉ／Ｆ７５に接続されている。
【００７４】
記憶装置７７としては、ハードディスクドライブ、フラッシュメモリ装置、磁気ディスク装置など様々な形式の記憶装置を使用することができる。
【００７５】
記憶装置７７またはＲＯＭ７３には、例えば、本実施形態で説明した処理を実現するアセンブリング前処理プログラム、連想配列格納部４３が格納されている。また、記憶装置７７またはＲＯＭ７３は、担当管理テーブル、Read配列、K-merインデックス部分テーブル５５、K-merインデックステーブル５６等を記憶することもできる。
【００７６】
ＣＰＵ７２は、記憶装置７７等に格納した本実施形態で説明した処理を実現するプログラムを読み出し、当該プログラムを実行する。具体的には、ＣＰＵ７２は、当該プログラムを実行することにより、取得部１１、担当判定部１２、登録部１５として機能する。
【００７７】
本実施形態で説明した処理を実現するプログラムは、プログラム提供者側から通信ネットワーク８０、および通信Ｉ／Ｆ７４を介して、例えば記憶装置７７に格納してもよい。また、本実施形態で説明した処理を実現するプログラムは、市販され、流通している可搬型記憶媒体に格納されていてもよい。この場合、この可搬型記憶媒体は読み取り装置７８にセットされて、ＣＰＵ７２によってそのプログラムが読み出されて、実行されてもよい。可搬型記憶媒体としてはＣＤ−ＲＯＭ、フレキシブルディスク、光ディスク、光磁気ディスク、ＩＣ（integrated circuit）カード、ＵＳＢ（Universal Serial Bus）メモリ装置など様々な形式の記憶媒体を使用することができる。このような記憶媒体に格納されたプログラムが読み取り装置７８によって読み取られる。
【００７８】
また、入力機器８２には、キーボード、マウス、電子カメラ、ウェブカメラ、マイク、スキャナ、センサ、タブレット、タッチパネルなどを用いることが可能である。また、出力機器８１には、ディスプレイ、プリンタ、スピーカなどを用いることが可能である。また、ネットワーク８０は、インターネット、ＬＡＮ、ＷＡＮ、専用線、有線、無線等の通信網であってよい。
【００７９】
なお、本実施形例では、シングルプロセッサを有する計算機を用いて、アセンブリング前処理を行ったが、マルチプロセッサを有する計算機を用いてアセンブリング前処理を行ってもよい。
【００８０】
本実施形態によれば、コンピュータクラスタ等の分散メモリ型のコンピュータシステムを用いて、K-merインデックステーブル作成のプロセスを並列化することができる。これにより、CPU当たりのメモリ消費量を削減することができる。また、CPU当たりの処理するK-merの数が削減される。ハッシュ値が完全に分散していることを条件に、プロセス数に比例して実行時間の短縮を図ることができる。また、各プロセスが完全に独立しているので、プロセス間においてリソースの競合の発生を回避することができる。これにより、処理速度の低下を防止することができる。また、あるコンピュータから複数のコンピュータに対して、各コンピュータが担当するK-merを振り分ける処理がないので、当該振分処理によるボトルネックの問題も生じない。
【００８１】
なお、本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【００８２】
１０ アセンブリング前処理装置
１１ 取得部
１２ 担当判定部
１３ 算出部
１４ 剰余判定部
１５ 登録部
１６ 部分配列判定部
１７ 配列位置登録部
１８ 連想配列格納部
２０ 配列位置格納部
２１ 生体配列情報
４０（４０−０〜４０−３） 計算機
４１（４１−０〜４１−３） ＣＰＵ
４２（４２−０〜４２−３） メモリ
４３（４３−０〜４３−３） 連想配列格納部
４４ 担当管理テーブル
５０ ストレージ装置
５１ ＣＰＵ
５２ メモリ
５３ 共有ディスク
５４ Read配列
５５ K-merインデックス部分テーブル
５６ K-merインデックステーブル
５７ ネットワーク
【技術分野】
【０００１】
本実施形態の一側面は、配列アセンブリングの前処理技術に関する。
【背景技術】
【０００２】
配列アセンブリングとは、バイオインフォマティクスにおいて短い塩基配列の断片から元の長い塩基配列を再構築することをいう。配列アセンブリングの１つに、De novo アセンブル（assemble）がある。De novo アセンブリとは、シーケンサ装置が出力したDNA（デオキシリボ核酸）、RNA（リボ核酸）等の生物配列（以下、「Read配列」と称する）を繋ぎ合わせて（assemble）、元の生物配列を再構築することをいう。ここで、シーケンサ装置とは、DNA/ RNA等の塩基配列を自動的に読み取る装置である。
【０００３】
アセンブル手法として、例えば、De Bruijn Graphによるアセンブルがある。De Bruijn Graphによるアセンブルでは、まず、Read配列をある長さの断片に細切れにした配列（生物配列断片）を生成する。以下では、生物配列断片を、「K-mer」と称する。次に、K-merからDe Bruijn Graphを作成する。そして、このDe Bruijn Graphについて、オイラーパス問題を解く（すなわち、De Bruijn Graphの全辺を通るパスを求める）。
【０００４】
De Bruijn Graphを作成する前処理として、K-merがRead配列のどこに存在するのかを管理するK-merインデックステーブルが作成されるが、正確なアセンブル処理を行うには、大量のRead配列を用いる。したがって、コンピュータを用いて、De Bruijn Graphを作成する場合、その前処理に用いるK-merインデックステーブルの作成に、大量のメモリ容量が消費される。
【０００５】
ところで、大量のデータを複数のサーバを用いて処理する技術の１つに、分散KVS（キーバリュー型データストア ： Key-Value Store）がある。分散KVSとは、キーと値からなる比較的単純な構造の連想配列を、多数のサーバで高速に処理するデータストアを示す。分散KVSでは、KVSクライアント装置が、キーの値に応じて、保存先のサーバ装置（KVSサーバ）を変えることで、複数のサーバに分散してデータを保存する。これにより、分散KVSでは、大量のデータをスケールアウト型で扱うことができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Daniel R. Zerbino and Ewan Birney “Velvet: Algorithms for de novo short read assembly using de Bruijn graph”, Genome Res., 2008 18: 821-829
【非特許文献２】“MEMCACHED”、[online] 、［平成23年11月15日検索］、インターネット、<http://memcached.org/>
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように、コンピュータを用いて、De Bruijn Graphを作成する場合、その前処理に用いるK-merインデックステーブルの作成に際して、例えば、数十〜数百ギガバイトのオーダで大量のメモリ容量が消費される。したがって、そのような膨大なデータを処理するために、処理時間が長くなる。
【０００８】
また、分散KVSを用いて、複数のKVSサーバにK-merインデックステーブルの作成を実行させる場合でも、KVSクライアントにそれらのKVSサーバに処理を分散させる処理が集中する。そのため、KVSクライアントでの分散処理がボトルネックとなり、処理の高速化を図ることができない可能性がある。
【０００９】
そこで、本実施形態の一側面によれば、生物配列断片のインデックス作成処理の高速化を図る情報処理装置を提供する。
【課題を解決するための手段】
【００１０】
本実施形態の一側面にかかるアセンブリング前処理装置は、取得部、担当判定部、登録部を含む。取得部は、生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する。担当判定部は、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する。登録部は、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報における部分配列情報の位置を示す位置情報を配列位置格納部に登録する。
【発明の効果】
【００１１】
本実施形態の一側面によれば、生物配列断片のインデックス作成処理の高速化を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】K-merインデックステーブルを説明するための図である。
【図２】K-merインデックステーブルの作成を説明するための図（その１）である。
【図３】K-merインデックステーブルの作成を説明するための図（その２）である。
【図４】本実施形態におけるアセンブリング前処理装置の構造の一例を示す。
【図５】本実施形態における複数のプロセスによる並列処理を実現する方法の一例を示す。
【図６】本実施形態におけるK-merインデックス作成処理の全体のフローを示す。
【図７】本実施形態の一実施例におけるアセンブリング前処理システムの一例を示す。
【図８】本実施形態の一実施例におけるK-merインデックス部分テーブル及びK-merインデックステーブルのデータ構造を示す。
【図９】本実施形態の一実施例における並列化された各プロセス（各計算機）が行うK-merインデックス部分テーブル作成処理フローを示す。
【図１０】本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。
【発明を実施するための形態】
【００１３】
図１は、K-merインデックステーブルを説明するための図である。図１の例では、Read配列は、上段より、Read配列０、Read配列１、Read配列３、Read配列４、・・・で示される。Read配列は、位置０〜位置２７までの２８個の塩基配列で表される。ここで、「A」はアデニンを示す。「G」はグアニンを示す。「T」は、チミンを示す。「C」は、シトシンを示す。
【００１４】
K-mer n（n=0，1，2，・・・）は、Read配列を1文字ずらしで長さKの文字列に区切った部分配列である。例えば、K-mer0は、Read配列０の位置０から６文字切り取った部分配列である。K-mer1は、Read配列０の位置１から６文字切り取った部分配列である。K-mer2は、Read配列０の位置２から６文字切り取った部分配列である。
【００１５】
このように、i番目のRead配列およびそのRead配列のｊ番目の位置によって、K-merがどのRead配列のどの場所に存在するかを特定することができる。このように、各K-merがどのRead配列のどの場所に存在するかの情報を保持するテーブルが、K-merインデックステーブルである。
【００１６】
図２及び図３は、K-merインデックステーブルの作成を説明するための図である。コンピュータを用いて、K-merインデックステーブルを作成する場合について考える。この場合、CPU（Central Processing Unit）は、Read配列を読み込むと、図２に示すように、Read配列の先頭から順次K-merを取得する。CPUは、順次取得したK-merをキーとし、K-merの位置情報（Read:i、Position:j）を値として、連想配列格納部に格納していく。ここで、位置情報（Read:i、Position:j）は、i番目のRead配列、およびそのRead配列のｊ番目の位置を示す。また、連想配列格納部はコンピュータ上のメモリに配置される。
【００１７】
例えば、K-mer0の場合、キーとして「ACGTGT」が格納され、値として「Read:0、Position:0」が格納される。例えば、K-mer1の場合、キーとして「CGTGTT」が格納され、値として「Read:0、Position:1」が格納される。例えば、K-mer2の場合、キーとして「GTGTTC」が格納され、値として「Read:0、Position:2」が格納される。
【００１８】
図３に示すように、Read配列から取得したK-mer（対象K-mer）と同一のK-mer（基準K-mer）が連想配列格納部に既に存在していた場合、CPUはK-merインデックステーブルに、基準K-merの位置情報と対象K-merの位置情報を関係付けて登録する。
【００１９】
例えば、「Read:0、Position:15」にあるK-mer「CGTGTT」を連想配列格納部に格納する場合について考える。この場合、K-mer「CGTGTT」は既に連想配列格納部に登録されているので、「Read:0, Position: 15」のK-merが「Read:0, Position: 1」のK-merと同一であることを示す情報をK-merインデックステーブルに登録する。
【００２０】
このようにして、連想配列格納部及びK-merインデックステーブルが作成される。
ところが、Read配列が大量に存在する場合、K-merも大量になり、大量のK-merを処理することになる。その結果、連想配列格納部が肥大化し、コンピュータ上のメモリを大量に消費することになる。また、コンピュータの処理量も増加するので、処理時間が長くなる可能性もある。
【００２１】
そこで、処理時間を短縮させるために、CPUの処理効率を向上させることが考えられる。例えば、複数のスレッドが同時に動作するマルチスレッド方式を用いた場合には、各スレッドが、自身が担当するRead配列について処理を行う。
【００２２】
しかしながら、マルチスレッド方式の場合、各スレッドは、同一プロセス内で動作しているため、メモリ空間を共有している。したがって、複数のスレッドは、共有メモリ上にある同一の連想配列格納部を更新することになる。そのため、例えば、連想配列格納部において、同じキーを有するエントリを更新する場合にはスレッド間の競合が生じるので、排他制御を行う。排他制御とは、あるスレッドに資源を独占的に利用させている間は、他のスレッドが利用できないようにする事で整合性を保つ処理をいう。
【００２３】
排他制御の結果、あるスレッドが資源を利用している間は、競合する他のスレッドはその利用が終了するまで待つことになり、待ち時間が発生する。そのため、処理時間が遅延する。
【００２４】
また、複数のスレッドを用いて処理をしても、各スレッドはプロセスメモリ空間を共有するため、プロセスメモリ空間を分離できない。したがって、プロセス当たりのメモリ使用量は変わらない。
【００２５】
そこで、プロセス当たりの処理量を軽減させる方法の１つとして、分散KVSを利用することが考えられる。しかしながら、分散KVSを用いて、複数のKVSサーバにK-merインデックステーブルの作成を実行させる場合でも、KVSクライアントにそれらのKVSサーバに処理を分散させる処理が集中する。そのため、KVSクライアントがボトルネックとなり、処理の高速化を図ることができない可能性がある。
【００２６】
そこで、本実施形態では、以下に説明するように、生物配列断片のインデックス作成処理の高速化を図る情報処理装置を提供する。
【００２７】
図４は、本実施形態におけるアセンブリング前処理装置の構造の一例を示す。アセンブリング前処理装置１０は、複数存在する。アセンブリング前処理装置１０は、取得部１１、担当判定部１２、登録部１５を含む。
【００２８】
取得部１１は、生物配列情報２１の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報（K-mer）を１文字ずつずらして取得する。取得部１１の一例として、図９のＳ１３、Ｓ１４の処理がある。生物配列情報２１は、シーケンサ装置が出力したDNA/ RNA等の生物配列（Read配列）である。
【００２９】
担当判定部１２は、アセンブリング前処理を実行するプロセスが部分配列情報に関するアセンブリング前処理を担当するか否かを判定する。担当判定部１２の一例として、図９のＳ１５〜Ｓ１７の処理がある。
【００３０】
登録部１５は、プロセスが部分配列情報に関するアセンブリング前処理を担当すると判定された場合、生物配列情報２１における部分配列情報の位置を示す位置情報を配列位置格納部２０に登録する。登録部１５の一例として、図９のＳ１８、Ｓ２０の処理がある。
【００３１】
このように構成することにより、各プロセスは、自身の担当するK-merを対象にしてK-merインデックステーブルを作成することができるので、プロセス当たりの処理量が減少すると共に、処理の並列化を図ることができる。したがって、生物配列断片のインデックス作成処理の高速化を図ることができる。
【００３２】
担当判定部１２は、算出部１３、剰余判定部１４を含む。
算出部１３は、部分配列情報のハッシュ値を算出し、ハッシュ値を第１の値で割ったときの剰余値を算出する。第１の値は、アセンブリング前処理装置の数、またはプロセス数を示す。ここでのプロセスとは、取得部１１、算出部１２、剰余判定部１３、部分配列判定部１４、及び登録部１５により実行される一連の処理を実行するプロセスを示す。算出部１３の一例として、図９のＳ１５、Ｓ１６の処理がある。
【００３３】
剰余判定部１４は、算出した剰余値が、第２の値であるか否かを判定する。剰余判定部１４の一例として、図９のＳ１７の処理がある。
【００３４】
このように構成することにより、K-merにより一意に処理を担当するプロセスが決定され、同一のK-merは、同一のプロセスにより処理することができる。
【００３５】
登録部１５は、部分配列判定部１６を含む。部分配列判定部１６は、算出した剰余値が第２の値であると判定された場合、取得した部分配列情報が、部分配列をキーとする連想配列を格納する連想配列格納部１８に登録されているか否かを判定する。部分配列判定部１６の一例として、図９のＳ１８の処理がある。連想配列格納部１８の一例として、連想配列格納部４３がある。
【００３６】
このように構成することにより、K-merインデックステーブル作成のために用いる連想配列を作成することができる。また、プロセス単位で連想配列格納部へK-merを登録することができるので、マルチスレッド方式を採用した場合の競合の問題も生じない。
【００３７】
登録部１５は、配列位置登録部１７を含む。配列位置登録部１７は、部分配列情報が連想配列格納部１８に登録されている場合、生物配列情報における部分配列情報の位置情報と、連想配列格納部に登録されている部分配列情報の生物配列情報２１における位置情報とを関係付けて配列位置格納部２０に登録する。配列位置登録部１７の一例として、Ｓ１９の処理がある。配列位置格納部２０の一例として、例えば、K-merインデックステーブル５６がある。
【００３８】
このように構成することにより、K-merインデックステーブルを作成することができる。
【００３９】
図５は、本実施形態における複数のプロセスによる並列処理を実現する方法の一例を示す。各プロセスは、ハッシュ関数を用いて、生体配列から読み出したK-merのハッシュ値を算出する。各プロセスは、そのハッシュ値をプロセス数で割った剰余に応じて、自身がそのK-merについてのK-merインデックステーブル作成処理を担当するか否かを判定する。そのプロセスがそのK-merについてのK-merインデックステーブル作成処理を担当すると判定した場合、そのプロセスは、そのK-merについてのK-merインデックステーブル作成処理を行う。これにより、K-merのハッシュ値をプロセス数で割った剰余に応じて、K-merについてのK-merインデックステーブル作成処理を担当するプロセスを動作させることができる。
【００４０】
例えば、図５に示すように、K-merインデックステーブル作成処理を４つのプロセスで行うとする。K-merインデックステーブル作成処理では、各プロセスは、自身が担当するK-merであると判定した場合、そのK-merが連想配列格納部に登録されていなければ、そのK-merを連想配列格納部に登録する。
【００４１】
各プロセスは、自身が担当するK-merであると判定した場合、そのK-merが連想配列格納部に登録されていれば、次の処理を行う。すなわち、そのプロセスは、K-merインデックステーブルにK-merの位置情報と、連想配列格納部２１に登録されているK-merの位置情報を関係付けて登録する。
【００４２】
なお、各プロセスは、自身の担当するK-merを判別するために、予め固有の値（担当No.）を保持している。例えば、図５の場合、プロセス０は、値０を有している。プロセス１は、値１を有している。プロセス２は、値２を有している。プロセス３は、値３を有している。K-merのハッシュ値をプロセス数で割った剰余が、各プロセスが予め有している値と同じであれば、そのプロセスがそのK-merについてのK-merインデックステーブル作成処理を担当する。
【００４３】
例えば、図５において、各プロセスは、Read配列からK-mer nを読み出し、ハッシュ関数を用いてK-mer nのハッシュ値を計算し、計算したハッシュ値を４で割った場合の剰余を計算する。剰余が０である場合、プロセス０がそのK-mer nについてのK-merインデックステーブル作成を担当する。
【００４４】
担当プロセスを決定するときの指標は、K-merのハッシュ値をプロセス数で割って得られる剰余以外でも、次の条件を満たせばよい。その条件とは、（１）K-merにより一意の値が決まる、（２）担当プロセスが少なくとも１つ存在する、（３）K-merがノード毎に十分に分散（一様分布に近ければ近いほどよい）である。
【００４５】
図６は、本実施形態におけるK-merインデックス作成処理の全体のフローを示す。上述の通り、各プロセスは、予め担当No.を有している。例えば、図６の場合、プロセス０（３１−０）は、担当No.として値０を有している。プロセス１（３１−１）は、担当No.として値１を有している。プロセス２（３１−２）は、担当No.として値２を有している。プロセス３（３１−３）は、担当No.として値３を有している。
【００４６】
各プロセス０〜３（３１−０〜３１−３）は、Read配列３０を読み込み、K-merインデックス部分テーブル作成処理Ｓ１（Ｓ１−０〜Ｓ１−３）を行う。ここで、K-merインデックス部分テーブル作成処理Ｓ１とは、次の処理をいう。すなわち、各プロセスは、Read配列３０から読み出したK-merのハッシュ値をハッシュ関数を用いて算出する。そのハッシュ値をプロセス数で割った剰余に応じて、そのプロセスが、自身が担当するK-merについての処理であるかを判定する。そのプロセスが担当するK-merについての処理であると判定した場合、そのプロセスは、そのK-merが連想配列格納部に登録されていなければ、そのK-merを連想配列格納部に登録する。そのK-merが連想配列格納部に登録されていなければ、そのプロセスは、次の処理を行う。すなわち、そのプロセスは、K-merインデックス部分テーブル３２（３２−０〜３２−３）にK-merの位置情報と、連想配列格納部に登録されているK-merの位置情報を関係付けて登録する。
【００４７】
各プロセス０〜３において、K-merインデックス部分テーブル作成処理Ｓ１（Ｓ１−０〜Ｓ１−３）の終了後、特定のプロセスは、次の処理を行う。すなわち、特定のプロセスは、各プロセスで作成されたK-merインデックス部分テーブルを連結して、K-merインデックステーブル３３を作成する（コンカーチネート処理Ｓ２）。なお、特定のプロセスは、プロセス０〜３のいずれかでもよいし、プロセス０〜３とは別のプロセスでもよい。
【００４８】
図７は、本実施形態の一実施例におけるアセンブリング前処理システムの一例を示す。アセンブリング前処理システムは、計算機４０（４０−０〜４０−３）及びストレージ装置５０を含む。計算機４０（４０−０〜４０−３）及びストレージ装置５０は、ネットワーク５７で接続されている。
【００４９】
計算機４０は、ＣＰＵ４１（４１−０〜４１−３）、メモリ４２（４２−０〜４２−３）を含む。ＣＰＵ４１は、計算機全体の動作を制御する。メモリ４２は、データを格納する記憶装置である。メモリ４２（４２−０〜４２−３）は、連想配列格納部４３（４３−０〜４３−３）を保持する。
【００５０】
計算機４０−０のメモリ４２−０は、さらに、担当管理テーブル４４を保持する。担当管理テーブル４４は、担当No.と、各計算機４０−０を識別する計算機識別情報とが関係付けられて格納されている。なお、担当管理テーブル４４のエントリをカウントすれば、プロセス数を得ることができる。
【００５１】
ストレージ装置５０は、ＣＰＵ５１、メモリ５２、共有ディスク５３を含む。ＣＰＵ５１は、ストレージ装置５０全体の動作を制御する。メモリ５２は、データを格納する記憶装置である。共有ディスク５３は、ネットワーク５７を介して、計算機４０−０〜４０−３が共有で利用する大容量記憶装置である。共有ディスク５３は、Read配列５４、K-merインデックス部分テーブル５５、K-merインデックステーブル５６を格納する。
【００５２】
図８は、本実施形態の一実施例におけるK-merインデックス部分テーブル及びK-merインデックステーブルのデータ構造を示す。K-merインデックス部分テーブル５５及びK-merインデックステーブル５６のデータ構造は同一であるので、以下では、K-merインデックス部分テーブル５５について説明する。
【００５３】
K-merインデックス部分テーブル５５は、「基準K-merのRead配列の番号」６１、「基準K-merのRead配列における位置」６２、「対象K-merのRead配列の番号」６３、「対象K-merのRead配列における位置」６４を含む。
【００５４】
ここで、基準K-merとは、連想配列格納部４３（４３−０〜４３−３）に格納されているK-merをいう。具体的には、基準K-merは、各プロセス（計算機４０）において処理を実行する場合に、各プロセス（計算機４０）でRead配列から１文字ずつずらして読み出して得られた同一のK-merのうち、最初に検出されたK-merのことである。
【００５５】
対象K-merとは、各プロセス（計算機４０）でRead配列から１文字ずつずらして読み出して得られた同一のK-merのうち、２番目以降に検出されたK-merのことである。
【００５６】
「基準K-merのRead配列の番号」６１及び「基準K-merのRead配列における位置」６２には、連想配列格納部４３（４３−０〜４３−３）に格納されているK-mer（基準K-mer）のRead配列の番号、及びそのRead配列における位置が格納される。
【００５７】
「対象K-merのRead配列の番号」６３、及び「対象K-merのRead配列における位置」６４は、基準K-merの検出後に検出された、基準K-merと同一のK-mer（対象K-mer）のRead配列の番号、及びそのRead配列における位置が格納される。
【００５８】
図９は、本実施形態の一実施例における並列化された各プロセス（各計算機）が行うK-merインデックス部分テーブル作成処理フローを示す。ＣＰＵ４１は、担当No.とプロセス数Ｐを取得する（Ｓ１１）。本実施形態では、ＣＰＵ４１−１〜４１−３は、計算機４０−０にアクセスして、自身の計算機識別番号をキーとして担当管理テーブル４４から自身の担当No.を取得し、担当管理テーブル４４のエントリをカウントしてプロセス数Pを取得する。計算機４０−０については、ＣＰＵ４１−０は、メモリ４２−０にアクセスし、自身の計算機識別番号をキーとして担当管理テーブル４４から自身の担当No.を取得し、担当管理テーブル４４のエントリをカウントしてプロセス数Pを取得する。ＣＰＵ４１−０は、担当No.として値０を取得する。ＣＰＵ４１−１は、担当No.として値１を取得する。ＣＰＵ４１−２は、担当No.として値２を取得する。ＣＰＵ４１−３は、担当No.として値３を取得する。なお、担当No.とプロセス数Ｐは、各計算機４０に予め設定しておいてもよい。なお、プロセス数Ｐは、本実施例では、４である。
【００５９】
ＣＰＵ４１は、初期化処理を行う（Ｓ１２）。すなわち、ＣＰＵ４１は、変数ｉ=０、ｊ＝０を設定すると共に、空の連想配列格納部４３を作成する。
【００６０】
ＣＰＵ４１は、ストレージ装置５０の共有ディスク５３にアクセスし、ｉ番目のRead配列５４を読み込む（Ｓ１３）。それから、ＣＰＵ４１は、そのｉ番目のRead配列におけるｊ番目のK-merを取得する（Ｓ１４）。
【００６１】
ＣＰＵ４１は、予めメモリ４２に展開したハッシュ関数を用いて、取得したK-merのハッシュ値Ｈを算出する（Ｓ１５）。ＣＰＵ４１は、算出したハッシュ値Ｈをプロセス数Ｐで割って得られる剰余を算出する（Ｓ１６）。
【００６２】
ＣＰＵ４１は、得られた剰余が、担当No.と等しいか否かを判定する（Ｓ１７）。得られた剰余が担当No.と等しくない場合（Ｓ１７で「Ｎｏ」）、Ｓ２１の処理に進む。得られた剰余が担当No.と等しい場合（Ｓ１７で「Ｙｅｓ」）、ＣＰＵ４１は、その取得したK-merが連想配列格納部４３に登録されているか否かを判定する（Ｓ１８）。
【００６３】
その取得したK-merが連想配列格納部４３に登録されていない場合（Ｓ１８で「Ｎｏ」）、ＣＰＵ４１は、その取得したK-mer（基準K-mer）の位置（ｉ，ｊ）を、連想配列格納部４３に登録する（Ｓ１９）。
【００６４】
その取得したK-merが連想配列格納部４３に登録されている場合（Ｓ１８で「Ｙｅｓ」）、ＣＰＵ４１は、次の処理を行う。ＣＰＵ４１は、取得したK-mer（対象K-mer）の位置（ｉ，ｊ）と、連想配列格納部４３に登録されているK-mer（基準K-mer）の位置とを関係付けて、ストレージ装置５０の共有ディスク５３内のK-merインデックス部分テーブル５５に登録する（Ｓ２０）。K-merインデックス部分テーブル５５は、ストレージ装置５０の共有ディスク５３内に計算機４０毎に構築される。
【００６５】
Ｓ１７で「Ｎｏ」の場合、またはＳ２０もしくはＳ２１の終了後、ＣＰＵ４１は、変数ｊをインクリメントする（Ｓ２１）。ＣＰＵ４１は、そのｉ番目のRead配列におけるｊ番目のK-merが存在するか否かを判定する（Ｓ２２）。
【００６６】
そのｉ番目のRead配列におけるｊ番目のK-merが存在する場合（Ｓ２２で「Ｙｅｓ」）、Ｓ１４の処理へ戻る。そのｉ番目のRead配列におけるｊ番目のK-merが存在しない場合（Ｓ２２で「Ｎｏ」）、ＣＰＵ４１は、変数ｉをインクリメントする（Ｓ２３）。
【００６７】
ＣＰＵ４１は、ｉ番目のRead配列が存在するか否かを判定する（Ｓ２４）。ｉ番目のRead配列が存在する場合（Ｓ２４で「Ｙｅｓ」）、Ｓ１４の処理へ戻る。ｉ番目のRead配列が存在しない場合（Ｓ２４で「Ｎｏ」）、本フローは終了する。
【００６８】
これにより、各プロセス（各計算機４０）で作成されたK-merインデックス部分テーブル５５が、ストレージ装置５０の共有ディスク５３内に格納される。
【００６９】
計算機４０−０は、ストレージ装置５０の共有ディスク５３内にある各プロセス（各計算機４０）で作成されたK-merインデックス部分テーブル５５を連結して、K-merインデックステーブル５６を作成し、共有ディスク５３に格納する。
【００７０】
なお、Ｓ２０において、ＣＰＵ４１は、対象K-merの位置と、基準K-merの位置とを関係付けて、ストレージ装置５０の共有ディスク５３内の、対応するK-merインデックス部分テーブル５５に登録したが、これに限定されない。例えば、各ＣＰＵ４１は、対象K-merの位置と、基準K-merの位置とを関係付けて、ストレージ装置５０の共有ディスク５３内の、共有のK-merインデックステーブル５５に登録するようにしてもよい。この場合、K-merインデックステーブル５５を管理するDBMS（DataBase Management System）によって、K-merインデックステーブル５５に対する各計算機４０からのエントリの追加処理が制御される。
【００７１】
図１０は、本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図である。コンピュータ７０は、本実施形態の処理を行うプログラムを読み込むことにより、アセンブリング前処理装置１０、または計算機４０として機能する。
【００７２】
コンピュータ７０は、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８、バス７９を含む。コンピュータ７０は、出力機器８１、及び入力機器８２と接続可能である。
【００７３】
ここで、ＣＰＵは、中央演算装置を示す。ＲＯＭは、リードオンリメモリを示す。ＲＡＭは、ランダムアクセスメモリを示す。Ｉ／Ｆは、インターフェースを示す。バス７９には、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８が接続されている。読み取り装置７８は、可搬型記録媒体を読み出す装置である。出力機器８１は、出力Ｉ／Ｆ７１に接続されている。入力機器８２は、入力Ｉ／Ｆ７５に接続されている。
【００７４】
記憶装置７７としては、ハードディスクドライブ、フラッシュメモリ装置、磁気ディスク装置など様々な形式の記憶装置を使用することができる。
【００７５】
記憶装置７７またはＲＯＭ７３には、例えば、本実施形態で説明した処理を実現するアセンブリング前処理プログラム、連想配列格納部４３が格納されている。また、記憶装置７７またはＲＯＭ７３は、担当管理テーブル、Read配列、K-merインデックス部分テーブル５５、K-merインデックステーブル５６等を記憶することもできる。
【００７６】
ＣＰＵ７２は、記憶装置７７等に格納した本実施形態で説明した処理を実現するプログラムを読み出し、当該プログラムを実行する。具体的には、ＣＰＵ７２は、当該プログラムを実行することにより、取得部１１、担当判定部１２、登録部１５として機能する。
【００７７】
本実施形態で説明した処理を実現するプログラムは、プログラム提供者側から通信ネットワーク８０、および通信Ｉ／Ｆ７４を介して、例えば記憶装置７７に格納してもよい。また、本実施形態で説明した処理を実現するプログラムは、市販され、流通している可搬型記憶媒体に格納されていてもよい。この場合、この可搬型記憶媒体は読み取り装置７８にセットされて、ＣＰＵ７２によってそのプログラムが読み出されて、実行されてもよい。可搬型記憶媒体としてはＣＤ−ＲＯＭ、フレキシブルディスク、光ディスク、光磁気ディスク、ＩＣ（integrated circuit）カード、ＵＳＢ（Universal Serial Bus）メモリ装置など様々な形式の記憶媒体を使用することができる。このような記憶媒体に格納されたプログラムが読み取り装置７８によって読み取られる。
【００７８】
また、入力機器８２には、キーボード、マウス、電子カメラ、ウェブカメラ、マイク、スキャナ、センサ、タブレット、タッチパネルなどを用いることが可能である。また、出力機器８１には、ディスプレイ、プリンタ、スピーカなどを用いることが可能である。また、ネットワーク８０は、インターネット、ＬＡＮ、ＷＡＮ、専用線、有線、無線等の通信網であってよい。
【００７９】
なお、本実施形例では、シングルプロセッサを有する計算機を用いて、アセンブリング前処理を行ったが、マルチプロセッサを有する計算機を用いてアセンブリング前処理を行ってもよい。
【００８０】
本実施形態によれば、コンピュータクラスタ等の分散メモリ型のコンピュータシステムを用いて、K-merインデックステーブル作成のプロセスを並列化することができる。これにより、CPU当たりのメモリ消費量を削減することができる。また、CPU当たりの処理するK-merの数が削減される。ハッシュ値が完全に分散していることを条件に、プロセス数に比例して実行時間の短縮を図ることができる。また、各プロセスが完全に独立しているので、プロセス間においてリソースの競合の発生を回避することができる。これにより、処理速度の低下を防止することができる。また、あるコンピュータから複数のコンピュータに対して、各コンピュータが担当するK-merを振り分ける処理がないので、当該振分処理によるボトルネックの問題も生じない。
【００８１】
なお、本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【００８２】
１０ アセンブリング前処理装置
１１ 取得部
１２ 担当判定部
１３ 算出部
１４ 剰余判定部
１５ 登録部
１６ 部分配列判定部
１７ 配列位置登録部
１８ 連想配列格納部
２０ 配列位置格納部
２１ 生体配列情報
４０（４０−０〜４０−３） 計算機
４１（４１−０〜４１−３） ＣＰＵ
４２（４２−０〜４２−３） メモリ
４３（４３−０〜４３−３） 連想配列格納部
４４ 担当管理テーブル
５０ ストレージ装置
５１ ＣＰＵ
５２ メモリ
５３ 共有ディスク
５４ Read配列
５５ K-merインデックス部分テーブル
５６ K-merインデックステーブル
５７ ネットワーク
【特許請求の範囲】
【請求項１】
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する取得部と、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定する担当判定部と、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する登録部と、
を備えることを特徴とするアセンブリング前処理装置。
【請求項２】
前記担当判定部は、
前記部分配列情報のハッシュ値を算出し、前記ハッシュ値を第１の値で割ったときの剰余値を算出する算出部と、
算出した前記剰余値が、第２の値であるか否かを判定する剰余判定部と、
を備えることを特徴とする請求項１に記載のアセンブリング前処理装置。
【請求項３】
前記登録部は、
前記算出した前記剰余値が前記第２の値であると判定された場合、前記取得した部分配列情報が、該部分配列をキーとする連想配列を格納する連想配列格納部に登録されているか否かを判定する部分配列判定部と、
を備えることを特徴とする請求項２に記載のアセンブリング前処理装置。
【請求項４】
前記登録部は、さらに、
前記部分配列情報が前記連想配列格納部に登録されている場合、前記生物配列情報における該部分配列情報の位置情報と、該連想配列格納部に登録されている部分配列情報の前記生物配列情報における位置情報と、を関係付けて前記配列位置格納部に登録する配列位置登録部
を備えることを特徴とする請求項３に記載のアセンブリング前処理装置。
【請求項５】
コンピュータに、
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得し、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定し、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する、
処理を実行させるアセンブリング前処理プログラム。
【請求項６】
アセンブリング前処理を担当するか否かの判定において、前記コンピュータは、
前記部分配列情報のハッシュ値を算出し、前記ハッシュ値を第１の値で割ったときの剰余値を算出し、
算出した前記剰余値が、第２の値であるか否かを判定する
処理を実行させる請求項５に記載のアセンブリング前処理プログラム。
【請求項７】
前記登録する処理において、前記コンピュータは、
前記算出した前記剰余値が前記第２の値であると判定された場合、前記取得した部分配列情報が、該部分配列をキーとする連想配列を格納する連想配列格納部に登録されているか否かを判定する
処理を実行させる請求項６に記載のアセンブリング前処理プログラム。
【請求項８】
前記登録する処理において、前記コンピュータは、
前記部分配列情報が前記連想配列格納部に登録されている場合、前記生物配列情報における該部分配列情報の位置情報と、該連想配列格納部に登録されている部分配列情報の前記生物配列情報における位置情報と、を関係付けて前記配列位置格納部に登録する
処理を実行させる請求項６に記載のアセンブリング前処理プログラム。
【請求項９】
アセンブリングの前処理を複数のコンピュータで実行するコンピュータクラスタシステムの制御方法であって、
前記複数のコンピュータのそれぞれは、
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得し、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定し、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する
ことを特徴とするコンピュータクラスタシステムの制御方法。
【請求項１】
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得する取得部と、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定する担当判定部と、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する登録部と、
を備えることを特徴とするアセンブリング前処理装置。
【請求項２】
前記担当判定部は、
前記部分配列情報のハッシュ値を算出し、前記ハッシュ値を第１の値で割ったときの剰余値を算出する算出部と、
算出した前記剰余値が、第２の値であるか否かを判定する剰余判定部と、
を備えることを特徴とする請求項１に記載のアセンブリング前処理装置。
【請求項３】
前記登録部は、
前記算出した前記剰余値が前記第２の値であると判定された場合、前記取得した部分配列情報が、該部分配列をキーとする連想配列を格納する連想配列格納部に登録されているか否かを判定する部分配列判定部と、
を備えることを特徴とする請求項２に記載のアセンブリング前処理装置。
【請求項４】
前記登録部は、さらに、
前記部分配列情報が前記連想配列格納部に登録されている場合、前記生物配列情報における該部分配列情報の位置情報と、該連想配列格納部に登録されている部分配列情報の前記生物配列情報における位置情報と、を関係付けて前記配列位置格納部に登録する配列位置登録部
を備えることを特徴とする請求項３に記載のアセンブリング前処理装置。
【請求項５】
コンピュータに、
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得し、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定し、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する、
処理を実行させるアセンブリング前処理プログラム。
【請求項６】
アセンブリング前処理を担当するか否かの判定において、前記コンピュータは、
前記部分配列情報のハッシュ値を算出し、前記ハッシュ値を第１の値で割ったときの剰余値を算出し、
算出した前記剰余値が、第２の値であるか否かを判定する
処理を実行させる請求項５に記載のアセンブリング前処理プログラム。
【請求項７】
前記登録する処理において、前記コンピュータは、
前記算出した前記剰余値が前記第２の値であると判定された場合、前記取得した部分配列情報が、該部分配列をキーとする連想配列を格納する連想配列格納部に登録されているか否かを判定する
処理を実行させる請求項６に記載のアセンブリング前処理プログラム。
【請求項８】
前記登録する処理において、前記コンピュータは、
前記部分配列情報が前記連想配列格納部に登録されている場合、前記生物配列情報における該部分配列情報の位置情報と、該連想配列格納部に登録されている部分配列情報の前記生物配列情報における位置情報と、を関係付けて前記配列位置格納部に登録する
処理を実行させる請求項６に記載のアセンブリング前処理プログラム。
【請求項９】
アセンブリングの前処理を複数のコンピュータで実行するコンピュータクラスタシステムの制御方法であって、
前記複数のコンピュータのそれぞれは、
生物配列情報の先頭から、K（Kは任意の整数）文字の文字列である部分配列情報を１文字ずつずらして取得し、
アセンブリング前処理を実行するプロセスが前記部分配列情報に関するアセンブリング前処理を担当するか否かを判定し、
前記プロセスが前記部分配列情報に関するアセンブリング前処理を担当すると判定された場合、前記生物配列情報における前記部分配列情報の位置を示す位置情報を配列位置格納部に登録する
ことを特徴とするコンピュータクラスタシステムの制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１３−１０６５６７（Ｐ２０１３−１０６５６７Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５４７６２（Ｐ２０１１−２５４７６２）
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]