JP2005500594A - 高速の近似部分文字列検索ための方法および装置 - Google Patents
高速の近似部分文字列検索ための方法および装置 Download PDFInfo
- Publication number
- JP2005500594A JP2005500594A JP2002588186A JP2002588186A JP2005500594A JP 2005500594 A JP2005500594 A JP 2005500594A JP 2002588186 A JP2002588186 A JP 2002588186A JP 2002588186 A JP2002588186 A JP 2002588186A JP 2005500594 A JP2005500594 A JP 2005500594A
- Authority
- JP
- Japan
- Prior art keywords
- database
- query
- sequence
- search
- score
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
- 238000000034 method Methods 0.000 title claims abstract description 90
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 67
- 230000008569 process Effects 0.000 claims description 21
- 230000006872 improvement Effects 0.000 claims description 19
- 238000005192 partition Methods 0.000 claims description 3
- 238000000638 solvent extraction Methods 0.000 abstract description 17
- 238000012856 packing Methods 0.000 abstract description 11
- 238000002869 basic local alignment search tool Methods 0.000 description 110
- 238000012545 processing Methods 0.000 description 26
- 108090000623 proteins and genes Proteins 0.000 description 24
- 102000004169 proteins and genes Human genes 0.000 description 21
- 238000005457 optimization Methods 0.000 description 13
- 108020004414 DNA Proteins 0.000 description 11
- 238000013459 approach Methods 0.000 description 10
- 238000004364 calculation method Methods 0.000 description 9
- 230000035945 sensitivity Effects 0.000 description 9
- 230000006870 function Effects 0.000 description 8
- 150000007523 nucleic acids Chemical class 0.000 description 7
- 239000002773 nucleotide Substances 0.000 description 7
- 210000004027 cell Anatomy 0.000 description 6
- 125000003729 nucleotide group Chemical group 0.000 description 6
- 210000000349 chromosome Anatomy 0.000 description 5
- 238000013515 script Methods 0.000 description 5
- 108091028043 Nucleic acid sequence Proteins 0.000 description 4
- 230000008901 benefit Effects 0.000 description 4
- 210000003917 human chromosome Anatomy 0.000 description 4
- 239000011159 matrix material Substances 0.000 description 4
- 238000012986 modification Methods 0.000 description 4
- 230000004048 modification Effects 0.000 description 4
- 108020004707 nucleic acids Proteins 0.000 description 4
- 102000039446 nucleic acids Human genes 0.000 description 4
- 108090000765 processed proteins & peptides Proteins 0.000 description 4
- 238000011160 research Methods 0.000 description 4
- 230000003068 static effect Effects 0.000 description 4
- 150000001413 amino acids Chemical class 0.000 description 3
- 230000027455 binding Effects 0.000 description 3
- 238000009739 binding Methods 0.000 description 3
- 230000007423 decrease Effects 0.000 description 3
- 230000000694 effects Effects 0.000 description 3
- 102000004196 processed proteins & peptides Human genes 0.000 description 3
- 238000012163 sequencing technique Methods 0.000 description 3
- 101100285983 Halobacterium salinarum (strain ATCC 700922 / JCM 11081 / NRC-1) htpX gene Proteins 0.000 description 2
- 238000004458 analytical method Methods 0.000 description 2
- 238000003491 array Methods 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 230000008878 coupling Effects 0.000 description 2
- 238000010168 coupling process Methods 0.000 description 2
- 238000005859 coupling reaction Methods 0.000 description 2
- 230000006837 decompression Effects 0.000 description 2
- 238000013461 design Methods 0.000 description 2
- 230000009977 dual effect Effects 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 101150002000 hsp-3 gene Proteins 0.000 description 2
- 238000002864 sequence alignment Methods 0.000 description 2
- 238000013518 transcription Methods 0.000 description 2
- 230000035897 transcription Effects 0.000 description 2
- 102100036008 CD48 antigen Human genes 0.000 description 1
- 238000001712 DNA sequencing Methods 0.000 description 1
- 241000255581 Drosophila <fruit fly, genus> Species 0.000 description 1
- 101000716130 Homo sapiens CD48 antigen Proteins 0.000 description 1
- 239000000654 additive Substances 0.000 description 1
- 230000000996 additive effect Effects 0.000 description 1
- 125000003275 alpha amino acid group Chemical group 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 239000003153 chemical reaction reagent Substances 0.000 description 1
- 239000002299 complementary DNA Substances 0.000 description 1
- 239000000470 constituent Substances 0.000 description 1
- 230000001351 cycling effect Effects 0.000 description 1
- 238000007405 data analysis Methods 0.000 description 1
- 238000007418 data mining Methods 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 238000002887 multiple sequence alignment Methods 0.000 description 1
- 230000008520 organization Effects 0.000 description 1
- 230000002085 persistent effect Effects 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 238000010845 search algorithm Methods 0.000 description 1
- 238000011524 similarity measure Methods 0.000 description 1
- 238000007619 statistical method Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
- 238000013519 translation Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
- G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G16B30/00—ICT specially adapted for sequence analysis involving nucleotides or amino acids
-
- G—PHYSICS
- G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
- G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G16B30/00—ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B30/10—Sequence alignment; Homology search
-
- G—PHYSICS
- G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
- G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G16B50/00—ICT programming tools or database systems specially adapted for bioinformatics
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y10S707/99936—Pattern matching access
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99941—Database schema or data structure
- Y10S707/99942—Manipulating data structure, e.g. compression, compaction, compilation
Landscapes
- Physics & Mathematics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Health & Medical Sciences (AREA)
- Engineering & Computer Science (AREA)
- Medical Informatics (AREA)
- General Health & Medical Sciences (AREA)
- Theoretical Computer Science (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Biotechnology (AREA)
- Evolutionary Biology (AREA)
- Biophysics (AREA)
- Spectroscopy & Molecular Physics (AREA)
- Chemical & Material Sciences (AREA)
- Analytical Chemistry (AREA)
- Proteomics, Peptides & Aminoacids (AREA)
- Bioethics (AREA)
- Databases & Information Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本発明は、高速配列データベース検索のためのＢＬＡＳＴアルゴリズムの実装における改良型を実行する、方法およびシステム（例えば、コモディティＢｅｏｗｕｌｆ型並列計算ハードウェア）を提供する。本発明はまた、クエリーパッキング、動的データベース分割、および改良型のヒット伸長のための方法およびシステムを提供する。本発明は、単一のデスクトッププロセッサにより実行される従来型のＢｌａｓｔアルゴリズムよりも２桁から３桁の規模で、より高速である改良型ＢＬＡＳＴアルゴリズムを実装するための一体型（ｃｏｍｂｉｎｅｄ）ハードウェア−ソフトウェアシステムを使用する、方法およびシステムを提供することによって、上記の要求および他の要求に取り組む。
Description
【技術分野】
【０００１】
（関連出願）
本出願は、「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｈｉｇｈ−Ｓｐｅｅｄ Ａｐｐｒｏｘｉｍａｔｅ Ｓｕｂ−Ｓｔｒｉｎｇ Ｓｅａｒｃｈｅｓ」と題する米国仮特許出願第６０／２８８，４６５号（２００１年５月４日出願）（この全体は、本明細書中にて参考として援用される）の優先権の利益を、米国特許法第１１９条（ｅ）項に基づき主張する。
【０００２】
（発明の分野）
本発明は、文字列検索に関連し、より具体的には、コンピュータに実装された、データベースの文字列検索に関する。
【背景技術】
【０００３】
（発明の背景）
核酸（例えば、ＤＮＡ）またはタンパク質の新規の並びが配列決定されると、その配列は、代表的には、既知の、ＤＮＡ情報およびタンパク質情報のデータベースに対して比較され、この新規ＤＮＡまたは新規タンパク質の機能の予備的な表示を提供する。次いで、研究者は、このデータベース検索の結果を評価するための実験を設計し得る。
【０００４】
ＤＮＡ配列決定技術の甚大な改善の結果として、ＤＮＡデータベースの増大する速度は、１９８９年の１年間当たり１５０万ヌクレオチドから１９９９年の１年間当たり１６億を超えるヌクレオチドへと、最近の１０年に亘って指数関数的に増大した。１９９９年以降、ショウジョウバエ、マウス、およびヒトのゲノムを含む全ゲノムが、配列決定されている。既知の遺伝的配列情報の量が指数関数的に増大するに従って、この増えつつある配列データベースを検索するための高速な方法の開発がますます重要なものとなった。
【０００５】
例えば、ゲノム情報の公的な集積機関である、ＧｅｎＢａｎｋは、現在、おおよそ、１６ＧＢのデータを所有している。これは、１９８２年において６８０Ｋにすぎなかったものから増大している（Ｂｅｎｓｏｎら，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２８（１：１５−１８（２０００）（ｗｗｗ．ｎｃｂｉ．ｎｌｍ．ｎｉｈ．ｇｏｖ／Ｇｅｎｂａｎｋ／ｇｅｎｂａｎｋｓｔａｔｓ．ｈｔｍｌもまた参照のこと））。この速度では、データ量は、１６．５ヶ月毎に２倍となる。２００１年だけでも、総計３ＧＢに及ぶ３５０万配列の新規配列が、ＧｅｎＢａｎｋに入力された。公開配列決定設備または専用配列決定設備の両方とも、２４時間体制でデータを生成するウェアハウス標準のファクトリーからなり、これは、試薬の利用および配列決定機器の速度にのみ制限される。
【０００６】
より多くの配列データが利用可能になると、最も根本的な問題の１つは、配列アライメント（すなわち、新たに発見された、ヌクレオチド配列またはアミノ酸配列が、それまでに既知でありかつ研究されているデータとどのような関係にあるかということ）である。いずれにしても、配列データ量が２倍になると、可能な比較の数は、４倍になるということに留意されたい。従って、おおよそ同じ時間経過で、コンピュータ速度が指数関数的に倍加する同様の印象があったとしても、配列比較アルゴリズムは、利用可能なデータの中いずれの有意な部分についての相同性を見出す能力において、ますます遅れをとっている。
【０００７】
相同性検索における現在の研究の多くは、より感度が高くかつより選択的であるアルゴリズムに集中しており、このアルゴリズムは、偽陽性および偽陰性の割合を低減するため、換言すると、微弱な相同性（例えば、遠縁の２つの生物の遺伝子）を正確に同定するため、例えば、以下に記載される、隠れマルコフモデルにような精巧な技術を使用するアルゴリズムである：Ｅｄｄｙ、「Ｐｒｏｆｉｌｅ Ｈｉｄｄｅｎ Ｍａｒｋｏｖ Ｍｏｄｅｌｓ」、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，１４（９）：７５５〜７６３（１９９８）（この全体は、本明細書中で参考として援用される）。このようなアルゴリズムは、利用可能なデータから最大量の情報を得ることのより高いレベルを求め、そして、おおいに研究的に興味深い。本発明は、異なった路線をとる。多くの用途について、既存のアルゴリズムは、十分良好である。特に、アルゴリズムにおけるＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ）ファミリ（ＮＣＢＩにより開発された）は、殆どの検索に対して十分に感度が高く、かつ選択的である。例えば、Ａｌｔｓｃｈｕｌら，「Ｇａｐｐｅｄ ＢＬＡＳＴ ａｎｄ ＰＳＩ−ＢＬＡＳＴ：ｎｅｗ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｏｔｅｉｎ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ｐｒｏｇｒａｍｓ」，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２５（１７）：３８９−３４０２（１９９７）（この全体は、本明細書中で参考として援用される））を参照のこと。
【０００８】
（ＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ））
現在、高速データベースの最も一般的な方法は、Ａｌｔｓｃｈｕｌら，Ｊ．Ｍｏｌ．Ｂｉｏｌ．，２１５（３）：４０３−１０（１９９０）（この全体が、本明細書中で参考として援用される）に記載されたＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ）の改良型である。ＢＬＡＳＴおよびその改良型は、高速な、配列のローカルアライメント（局所的アライメント）を提供する。ＢＬＡＳＴプログラムは、タンパク質またはＤＮＡのクエリー（問合せ配列）と、タンパク質またはＤＮＡのデータベースとを、任意の組み合わせで比較するように記述されており、ここで、ＤＮＡ配列は、これらの任意の比較が実行される前に、概念上の翻訳をしばしば受ける。
【０００９】
ＢＬＡＳＴは、類似性の指標を最適化することを試みるヒューリスティック（発見的）なものである。具体的に、ＢＬＡＳＴは、ランダムなアライメントとは統計学的に区別され得る類似性のある全ての局所領域（ハイスコアセグメントペア（Ｈｉｇｈ−ｓｃｏｒｉｎｇ Ｓｅｇｍｅｎｔ Ｐａｉｒ）（ＨＳＰ）と呼ばれる）を同定する。ＢＬＡＳＴは、「閾値」パラメータであるＴを設定することによって、速度と感度との間の折り合いを可能にする。より高い値のＴによって、より高速となるが、また、微弱な類似性を取りこぼす可能性も増大させる。このＢＬＡＳＴプログラムは、クエリーの長さと検索されるデータベースの積に比例して時間を必要とする。
【００１０】
ＢＬＡＳＴアルゴリズムの中心的な概念は、統計的に有意なアライメントは並置されたワードのＨＳＰを含む可能性が高いということである。ＢＬＡＳＴは、まずはじめに、このクエリー配列内のいくつかのワードと並置されたときに少なくともＴのスコアを持つワード（例えば、タンパク質に対して３、ＤＮＡについて１２のワード）についてデータベースをスキャンする。この条件を満たす並置された任意のワードペアは、「ヒット」と呼ばれる。このアルゴリズムの第２の工程によって、各ヒットが、アライメントの中に報告されるのに十分なスコアで存在するか否かを評価される。これは、実行中のアライメントのスコアがそれまでに得た最大値からＸよりも低下するまで、両方向へヒットを伸長させていくことにより実行される。
【００１１】
その殆どの基本的な実装において、このＢＬＡＳＴアルゴリズムは、以下の３つの工程を実行する：（１）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルし；（２）データベース中の配列の各々に対して、閾値Ｔよりも高いスコアを有するワードヒット（すなわち、データベースの配列の中のワードと一致するクエリー配列に由来するワード）をスキャンし；（３）ワードヒットの各々について、Ｓ以上のスコアのハイスコアペア（ＨＳＰ）を形成するように両方向にワードヒットを伸長していく。以下のパラグラフで、これらの工程を詳細に説明する。
【００１２】
代表的なＢＬＡＳＴの実装において、ハイスコアワードのリストがｉ行×ｊ列のルックアップテーブルの中に作成され、ここで、ｉは、長さｗの可能なワードの全ての数であり、そして、ｊは、（クエリー配列におけるエレメントの数）−ｗである。値ｉは、長さｗの全ての可能なワードを表すので、このルックアップテーブルにおける行の各々は、長さｗの１つのワードに対応する。この行番号は、その対応するワードの字句順序（ｌｅｘｉｃａｌ ｏｒｄｅｒ）に対応し、そして、これはそのワードに関する「行番号」とみなされ得る。ＤＮＡ配列に関して、ｉ＝４ｗであり；タンパク質配列に関して、ｉ＝２０ｗである。このｊ値は、クエリー配列の中の、長さｗであるワードの開始位置の番号を表す。このルックアップテーブルは、全て０として初期化され、次いで、以下のように配置（ｐｏｐｕｌａｔｅ）される：クエリー中の長さｗのワードそれぞれについて、その対応する行を参照する。この行ｘを呼びだす。クエリー配列ｙにおけるワードの位置を呼び出す。このルックアップテーブルの（ｘ，ｙ）要素をｙに設定する。一旦、このルックアップテーブルが配置されると、次いで、取り除かれる（ｔｒｉｍ）。全て０を有する行は、クエリーにおいて存在しないワードを表すので、取り除かれる。次いで、残りのワードは、それらのワードを調べてこれらのセルフ類似性スコアが最小閾値Ｔを満たすか否かを判断することによって、有意性についてスクリーニングされる。類似性スコアは、代表的には、以下に記載されるような置換マトリックス（例えば、ＰＡＭ１２０およびＢＬＯＳＵＭ６２）を使用して計算される：Ｄａｙｈｏｆｆら，Ａｔｌａｓ ｏｆ Ｐｒｏｔｅｉｎ Ｓｅｑｕｅｎｃｅ ａｎｄ Ｓｔｒｕｃｔｕｒｅ，Ｖｏｌ．５，Ｓｕｐｐｌ．３，Ｅｄ．Ｍ．Ｏ．Ｄａｙｈｏｆｆ（１９７８）；Ｈｅｎｉｋｏｆｆ ａｎｄ Ｈｅｎｉｋｏｆｆ，Ｐｒｏｃ．Ｎａｔｌ．Ａｃａｄ Ｓｃｉ．ＵＳＡ，８９：１０９１５−１０５１９（１９９２）；ならびにＨｅｎｉｋｏｆｆおよびＨｅｎｉｋｏｆｆ，Ｐｒｏｔｅｉｎｓ，１７：４９−６１（１９９３）。これらの刊行物は、本明細書中において、参考としてその全体が援用される。Ｔ未満のセルフスコアを有するワードを表す行は、削除される。最終的に、ゼロ（０）を有する全ての列が取り除かれる。得られたルックアップテーブルは、有意なワードの字句ワード数（ｌｅｘｉｃａｌ ｗｏｒｄ ｎｕｍｂｅｒ）によって、索引付けされ、そして、クエリー配列における有意なワードの位置を戻す。
【００１３】
ＢＬＡＳＴはヒューリスティックアルゴリズムであり、そして、ｗおよびＴの値は、感度、特異性、および速度の最適な組み合わせについて選択される。所定値Ｔについてｗが増加すると、特異性は向上するが、感度は低下する。同様に、所定値ｗについてＴが減少すると、感度は向上するが、特異性は低下し、実行時間は増大する。ｗおよびＴの例示的な設定は、タンパク質について、ｗ＝４、Ｔ＝１７であり、ＤＮＡについては、ｗ＝１２，Ｔ＝６０である。
【００１４】
一旦、このルックアップテーブルが構築されると、これは、クエリー配列をこのデータベースに対して比較するために使用される。具体的には、このデータベースは、そのセルフスコアは閾値Ｔよりも高いクエリー配列の中に存在する長さｗの全てのワードに対して検索される。従って、見出された全てのワードは、「ヒット」と称される。データベース検索の出力（アウトプット）は、ヒットのリストを含む。このデータベースが反復して検索されるので、このデータベースは、クエリー配列に対して生成されたルックアップテーブルに類似の、ルックアップテーブルへと前処理される。従って、この検索プロセスは、２つのルックアップテーブルを比較することによって、迅速に実施され得る。
【００１５】
この最終工程は、各ヒットを伸長させてハイスコアセグメントペア（ＨＳＰ）を形成することである。代表的には、このヒットは、クエリー配列およびデータベース配列の対応する並び（ストレッチ）の間の類似性スコアが予め決定した閾値Ｓ未満に低下するまで、両方向に伸長される。代表的なＢＬＡＳＴ実装の出力は、このデータベースにおいて見出されたヒットの記述を含む。ヒットの各々に対して、この出力は、ヒットが現れた配列についての情報、そのヒットのビットスコア、与えられたＨＳＰが偶然に見出される確率、およびＥ値（これは、この与えられたスコアに関して、このサイズのデータベースにおいて偶然に見出されたと期待される一致の数の指標である）を含む。
【００１６】
（ＢＬＡＳＴにおける以前の改良）
ＢＬＡＳＴアルゴリズムの実装は、このアルゴリズムが最初に導入されたとき以来、改良を受けている。３つの主要な改良として、ヒット伸長のための「ツー・ヒット（ｔｗｏ−ｈｉｔ）」法、ギャップ付きアライメントを生成する能力、および微弱であるが生物学的に関連性にある配列類似性に対して多くの場合においてより感度が高い「ＰＳＩ−ＢＬＡＳＴ（Ｐｏｓｉｔｉｏｎ−Ｓｐｅｃｉｆｉｃ ｉｔｅｒａｔｅｄ ＢＬＡＳＴ）」が挙げられる。これらの改良型は、例えば、Ａｌｔｓｃｈｕｌ，「Ｇａｐｐｅｄ ＢＬＡＳＴ ａｎｄ ＰＳＩ−ＢＬＡＳＴ：ａ ｎｅｗ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｏｔｅｉｎ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ｐｒｏｇｒａｍｓ」，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２５（１７）：３３８９〜３４０２（１９９７）に詳細に説明されている。
【００１７】
オリジナルのＢＬＡＳＴの実装の性能データは、その伸長工程（ここでは、ヒットが伸長されてＨＳＰを生成する）が処理時間の最大量を費やしたことを示している。ヒットの伸長のための「ツー・ヒット」法は、この工程における改良であり、この改良によって、費やす時間がずっと短い伸長工程が作り出される。実験的証拠によって、目的とする代表的なＨＳＰは、単独のワードペアよりもずっと長く、それに従って、同じ対角線（ｄｉａｇｏｎａｌ）上で互いに比較的短い距離内に複数のヒットを含み得ることが示されている。このツー・ヒット法は、伸長が始まる前に、同じ対角線上にあり、かつ互いに距離Ａの内にある、２つの重なっていないワードペアの存在を必要とすることによって、この観察結果を利用する。最も新しいヒット（ｔｈｅ ｍｏｓｔ ｒｅｃｅｎｔ ｏｎｅ）と重なっているヒットは全て、無視される。この方法は、伸長をすすめるために１つのヒットではなく、２つのヒットを必要とするので、この閾値パラメーターＴは、同等の感度を保持するほど低くなければならない。この効果は、多くの単独のヒットが見出されるが、少数の部分のみが、伸長を引き起こす同一の対角成分上において随伴する第２のヒットを有するということである。従って、ヒットのかなり多くの部分は、適切な対角成分について、最も近いヒットの座標（ｃｏｏｒｄｉｎａｔｅ）を調べ、その最も近いヒットが、そのときのヒットの座標から距離Ａ内にあるか否かを評価し、そして、最後に、新しい座標でこの座標を置換するという僅かな計算の後に、簡単に処理を終了し得る。経験的に、少ない伸長を必要とすることによって省かれる計算量によって、より多くのヒット数を処理するために必要とされる余分な計算量が相殺される。
【００１８】
この伸長工程を実施する別の方法が、例えば、以下に記載されている：「Ｍｕｌｔｉｐｌｅ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ ｕｓｉｎｇ ｂｌｏｃｋ ｃｈａｉｎｉｎｇ」、Ｚｈｅｎｇ Ｚｈａｎｇ，博士論文，Ｔｈｅ Ｐｅｎｎｓｙｌｖａｎｉａ Ｓｔａｔｅ Ｕｎｉｖｅｒｓｉｔｙ，ＵＭＩ Ｄｉｓｓｅｒｔａｔｉｏｎ Ｓｅｒｖｉｃｅｓ，Ａｎｎ Ａｒｂｏｒ（１９９６）；およびＺｈａｎｇら、「Ｃｈａｉｎｉｎｇ ｍｕｌｔｉｐｌｅ−ａｌｉｇｎｍｅｎｔ ｂｌｏｃｋｓ」，Ｊ．ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ，１：２１７− ２２６（１９９４）。この方法は、有向閉路グラフに関する古典的な最適経路アルゴリズムの特別な場合である、「ブロック連鎖」として知られているコンピュータ科学の既知のクラスの問題に対する伸長工程の類似性に基づいている。上述の方法は、Ｋ−Ｄツリーと称されるより高い次元の計算幾何学の周知の技術を採用する。一般的に、Ｋ−Ｄツリーは、セルが、過剰の入力オブジェクト含まないように、相対的に小さい数のセルへと多次元空間を階層的に分解するために使用される（Ｂｅｎｔｌｅｙ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１８：５０９−５１７，（１９７５）（これの全体が、本明細書中で参考として援用される）を参照のこと）。Ｚｈａｎｇにおいて、Ｋ−Ｄツリーを使用して、可能なブロック鎖の空間を領域へと分解するのに使用され、従って、このブロック連鎖問題を、連鎖領域（ｃｈａｉｎｉｎｇ ｒｅｇｉｏｎ）の計算機的にはそれ程負荷がかからない問題へと単純な形にする。Ｋ−Ｄツリーの使用によって、複数の配列比較（すなわち、２つを超える配列が、互い比較される）にとって有意な計算的利得を提供する。
【００１９】
ギャップ付きアライメントを生成する能力によって、ＢＬＡＳＴ性能における有意な改良が可能となる。オリジナルＢＬＡＳＴプログラムは、一緒に考えた場合のみにおいて、統計学的に有意な単独のデータベース配列を含むいくつかのアライメントをしばしば見出す。これらのアライメントのうちの任意の１つを見落とすことによって、全てを含めた結果に支障をきたす。ギャップ付きアライメントを生成するためのアルゴリズムを導入することによって、有意な全てを含めた結果において、部分的にまとめられたギャップなしのアライメントよりもただ１つののみを見出すことが必然となる。これによって、パラメータＴが上昇することを可能にし、初期データベーススキャンの速度を向上させる。ギャップ付きアライメントを生成する１つの方法は、ヒューリスティックアプローチ（これは、ＨＳＰを構築するためのＢＬＡＳＴ法におけるありふれた生成法である）を使用する。このアプローチの中心的な概念は、５０データベース配列ごとに、おおよそ１を超えない伸長が生じるように選択した、中程度のスコアＳｇを超える任意のＨＳＰについてギャップ付きの伸長を引き起こすことである。統計学的な分析によって、Ｓｇが、代表的な長さのタンパク質クエリーに対して約２２ビットで設定されるべきであることが示されている。ギャップ付き伸長は、ギャップのない伸長よりも長く実行するための時間を必要とするが、極少数のギャップ付き伸長を実行することによって、ギャップ付き伸長が費やす、総実行時間に占めるその割合は比較的に低く押さえら得る。さらに、ギャップのないアライメントのコレクションというよりも、単一のギャップ付きアライメントを探索することによって、構成するＨＳＰのうちの１つのみが、首尾よく生成された総合した結果について位置付けられる必要がある。これは、任意の単一の中程度のスコアをもつＨＳＰを失う可能性がずっと高いことを、許容され得ることを意味する。これによって、このアルゴリズムのヒットステージについてのパラメータを実質的に上昇させることを可能にするが、他方、匹敵する感度を保持している。例えば、Ｔは、オリジナルＢＬＡＳＴ実装の１ヒットヒューリスティックに関して、１１〜１３に向上した。
【００２０】
位置特異的スコアマトリクス（プロファイルまたはモチーフとして知られている）に対してＢＬＡＳＴを反復適用することによって、微弱であるが、生物学的に有意な関係がかなり頻繁に検出されるデータベース検索が可能となる。ＰＳＩ−ＢＬＡＳＴと称される位置特異的であって、反復されるＢＬＡＳＴの１つの実装は、最初のＢＬＡＳＴ実行の出力から位置特異的スコアマトリックスを構築し、その後のＢＬＡＳＴ実行のためのクエリーとしてそのマトリックスを使用する。
【００２１】
いくつかの精緻化が、ＢＬＡＳＴの現行の実装の、その速度、感度、および特異性を、そのオリジナルと比較したときに３倍を超えるまで向上させてきたが、配列データベースの増大の指数関数的な速度は、このアルゴリズムの実装に対しての絶え間ない改善を必要としている。
【００２２】
（並列処理）
大規模データベース検索を高速化するための１つのアプローチは、並列処理を使用することである。高性能並列計算（ハイパフォーマンスパラレルコンピューティング）は、複数のプロセッサにまたがって、大規模で複雑なタスクを分割することによって達成される。１つの単純な例として、配列データベースは、いくつかの部分（パート）へと細分化され得、各部分は、特定の処理単位へと割り当てられ得る。次いで、同じクエリーが、同時に、全ての処理単位において実行され得、各処理単位は、そのデータベースの一部分のみを検索する必要がある。より複雑な例として、タスクがサブタスクに分割される。例えば、ＢＬＡＳＴにおける伸長工程は、ＨＳＰの選択的な鎖について膨大な吟味を必要としている。この例においては、可能な鎖の空間は、複数の部分空間に細分化され、そして、部分空間の各々は、別個のプロセッサに割り当てられる。
【００２３】
様々な方法を使用して、複数の計算機（コンピュータ）における効率の改善が達成され得るが、並列処理を組織化し、かつそれを調整する最も一般的な方法は、目前にある問題を自動的に分解し、そして、プロセッサが、これらの作業を実行している間に、必要とされる場合に相互通信することを可能にするコードを記述することである。上記の第１の例において、プロセッサが、データベースの部分において、クエリーに対するマッチ（一致）を見出すと、このプロセッサは、それらの検索を実行している他のプロセッサに、そのイベントを信号で送信し得る。上記に第２の例において、プロセッサが新たな最大スコアを見出した場合に、そのプロセッサは、そのイベントを信号で送信し得、その結果、他のプロセッサは、それらの閾値を上昇させる。
【００２４】
並列処理の殆どのアプリケーションは、通常、プロセッサ間である程度の相互作用を必要とし、したがって、それらのプロセッサは、情報を交換するために相互に通信し得なければならない。例えば、マップ上のセルに対する値は、それらの最近接セルの値に依存し得る。このマップが２つの部分に分解されるとき、各々は、別個のＣＰＵ上で処理され、このプロセッサは、セル値を、そのマップの隣接エッジにおけるセル値と交換しなければならない。同様に、配列アライメントがいくつかのローカルアライメントに分解される場合、各ローカルアライメントを取り扱うプロセッサの各々は、その元の境界を越えてアライメントを伸長させるために、隣接するアライメントを取り扱うプロセッサと通信し得なければならない。
【００２５】
並列処理に対するいくつかの対照的なアプローチが存在する。例えば、並列処理は、高度に専用化したハードウェアまたは商用既製（ｃｏｍｍｅｒｃｉａｌ ｏｆｆ−ｔｈｅ−ｓｈｅｌｆ；ＣＯＴＳ）ハードウェア上にて実施され得る。ＢＬＡＳＴおよび他の配列比較およびデータベース検索のアルゴリズムアルゴリズムは、高度に専用化した、並列処理ハードウェア（例えば、ＰＡＲＡＣＥＬ’Ｓ ＧＥＮＥ ＭＡＴＣＨＥＲマシン）において実装されている。Ｕｌｌｎｅｒの米国特許第６，１１２，２８８号（この全体が、本明細書中で参考として援用される）に記載されるように、ＰＡＲＡＣＥＬ製ＧＥＮＥ ＭＡＴＣＨＥＲは、プログラム可能な特別目的のパイプラインプロセシングシステムを使用し、このシステムは、複数のアクセラレータチップを直列接続して備える。このアクセラレータチップの各々は、インストラクションプロセッサを備える。このパイプラインプロセッサセグメントの各々は、複数のパイプラインプロセッサを直列接続して備える。このように専用ハードウェアは、有意な速度向上を提供し得、特に、ダイナミックプログラミング（ＤＰ）アルゴリズムに関して有意な速度向上を提供し得る。
【００２６】
この専用ハードウェアアプローチと対照的なのは、コモディティ並列処理アプローチであり、これは、安価な商用既製（「ＣＯＴＳ」）ハードウェアを使用する。コモディティ並列処理にとって一般に普及しているアプローチは、以下に説明されるようなＢｅｏｗｕｌｆクラスタである：Ｂｅｃｋｅｒら，Ｂｅｏｗｕｌｆ：Ａ Ｐａｒａｌｌｅｌ Ｗｏｒｋｓｔａｔｉｏｎ ｆｏｒ Ｓｃｉｅｎｔｉｆｉｃ Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｒｏｃｅｅｄｉｎｇｓ，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ Ｐｒｏｃｅｓｓｉｎｇ（１９９５）；およびＭ．Ｓ．Ｗａｒｒｅｎら，Ｐａｒａｌｌｅｌ ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ ｗｉｔｈ ｃｏｍｍｏｄｉｔｙ ｃｏｍｐｏｒａｅｎｔｓ；Ｈ．Ｒ．Ａｒａｂｎｉａ編，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ（ＰＤＰＴＡ’９７），１３７２−１３８１頁，１９９７（これらの刊行物は、本明細書中で、それらの全体が参考として援用される）。Ｂｅｏｗｕｌｆ型クラスタは、専用高速ネットワークによって相互接続されたコモディティハードウェアコンポーネント（ＬｉｎｕｘまたはＦｒｅｅＢＳＤのようなフリーソフトウェアである基本ソフト（ＯＳ）を動作させる）から主に構築される、高性能の、大規模並列計算機である。代表的なＢｅｏｗｕｌｆ型クラスタは、ハイパフォーマンスコンピューティングタスクの実行専用の、複数の相互接続した、ＰＣまたはワークステーションを備える。これは、通常、シングルノードのみを介して、外部と接続されている。代表的なＢｅｏｗｕｌｆ型クラスタは、メッセージパッシングと称されるプロセッサ間通信の一般に普及している方法を使用する。メッセージパッシングの一般に普及している実装は、「ＰＶＭ（Ｐａｒａｌｌｅｌ Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ）」および「ＭＰＩ（Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ Ｉｎｔｅｒｆａｃｅ）」を含む。
【発明の開示】
【発明が解決しようとする課題】
【００２７】
コモディティ並列処理ハードウェアは、妥当なコストでかなりの性能を提供し、かつ、指数関数的なデータベースの増大がデータベース検索における実質的な改良を必要としているために、コモディティ並列処理ハードウェア上のＢＬＡＳＴアルゴリズムの性能を向上させるようにＢＬＡＳＴアルゴリズムを改良する必要性が存在する。
【課題を解決するための手段】
【００２８】
（発明の要旨）
本発明は、単一のデスクトッププロセッサにより実行される従来型のＢｌａｓｔアルゴリズムよりも２桁から３桁の規模で、より高速である改良型ＢＬＡＳＴアルゴリズムを実装するための一体型（ｃｏｍｂｉｎｅｄ）ハードウェア−ソフトウェアシステムを使用する、方法およびシステムを提供することによって、上記の要求および他の要求に取り組む。本発明システムのソフトウェアコンポーネントは、本明細書中において、Ｐａｒａｃｅｌ ＢＬＡＳＴと称され、そしてそのハードウェアコンポーネントは、本明細書中において、Ｐａｒａｃｅｌ ＢｌａｓｔＭａｃｈｉｎｅとして称される。本明細書中で教示される技術に従って、このＢｌａｓｔＭａｃｈｉｎｅ上でのＰａｒａｃｅｌ ＢＬＡＳＴによって、ゲノム規模のデータセットの操作が可能であり得る。アルゴリズム的な改良および並列ハードウェアアーキテクチャによって、このＢｌａｓｔＭａｃｈｉｎｅが、他の技術を用いて解決可能な問題よりも、重大で大きな問題を解決することを可能とする。１つの実施形態において、このシステムは、ゲノムの第１のパス分析について十分適しており、これにより、その後の段階における、より精巧な遅いアルゴリズムおよび手動による介入を可能にして、この第１のパスが残していたギャップを満たすことを可能にする。
【００２９】
１つの局面において、本発明は、データベース検索を並列化するために、動的データベース分割を実行するための、構造体おひよび方法を提供する。
【００３０】
別の局面において、本発明は、単一のデータベース検索に対して複数のクエリーを併用するための、構造体および方法を提供する。
【００３１】
別の局面において、本発明は、クエリー配列とデータベース配列との間のより長いマッチを生成するためのハイスコアセグメントペアの十分な、連結および伸長のための構造体および方法を提供する。
【００３２】
１つの特定の実施形態において、本発明は、配列データベースに対して複数のクエリー配列を比較する為の方法に関し、この方法は、以下の工程を包含する：（ａ）複数のクエリー配列を、一体型クエリー配列に結合する工程；（ｂ）上記データベースの複数の下位区分を決定する工程；（ｃ）複数の検索を実施する工程であって、ここで、各検索は、上記データベースの複数の下位区分のうちの１つに対して一体型クエリー配列の比較を含む工程であって、これによって、複数のワードマッチを生成した工程；（ｄ）工程（ｃ）において生成された複数のワードマッチの長さを伸長する工程であって、複数のハイスコアセグメントペアを生成する工程；（ｅ）上記の複数のハイスコアセグメントペアを結合する工程；および（ｆ）複数のレーポートを作成する工程であって、各レポートは、複数のクエリー配列の１つに対する最もスコアの高いマッチ（一致）を示す工程。
【００３３】
複数の配列は、任意の方法による一体型クエリー配列へと結合され得る。例えば、本発明の方法の工程（ａ）において、複数に配列は、クエリールックアップテーブルに複数の配列を記憶すること、およびクエリー番号で上記配列の各々について索引作成し、それぞれのクエリー番号と上記の各配列を連結することによって、一体型クエリーに結合される。この結合プロセスは、任意の適切なパラメータ（例えば、長さパラメーター）を使用して、制御またはモニターされ得る。より具体的には、複数の配列は、上記テーブルに記憶されたデータ量が予め決定されていた制限値に達するまで、クエリールックアップテーブルにおいて記憶され得る。別の例において、本発明の方法の工程（ａ）において、複数の配列は、同時に複数のクエリーのハッシュを構築することによって、結合され得る。
【００３４】
このデータベースは、任意の適切な方法によって、複数の下位区分に分割され得る。例えば、このデータベースの複数の下位区分を決定する工程は、塩基数、および上記のデータベース中の配列の数で、上記のデータベースのサイズを特定して、このデータベースを検索することによって生成される結果に関する統計的に有意な値を計算する工程を包含する。他の例において、このデータベースは、ＢＬＡＳＴアルゴリズムに対して１以上の、以下の改変を行うことによって複数の下位区分に分割され得る：（ｉ）基礎的なＢＬＡＳＴアルゴリズムの少なくとも１つの統計学的パラメーターは、正しい部分的な結果を生成するように調整され；（ｉｉ）データベースにアクセスするための基礎的なＢＬＡＳＴアルゴリズムにおいて使用される入力／出力ルーチンのうちの少なくとも１つが、データベースのサブセットにアクセスすることを支援するように改変され；（ｉｉｉ）中間結果の複数のメモリイメージ（ｍｅｍｏｒｙ ｉｍａｇｅ）が生成され；そして／または（ｉｖ）このメモリイメージが再結合されて、単一の結合されたＢＬＡＳＴレポートを作成する。特定の実施形態において、この基礎的なＢＬＡＳＴアルゴリズムは、データベースのサイズおよびこのデータベース中の配列数の両方を特定して、このデータベースを検索することによって生成された結果の統計学的な有意性を計算するように調整される。別の特定の実施例において、コマンドラインで引数（−ｚ）を使用して、このデータベース全体の塩基のサイズを特定し、そして、コマンドラインオプション（−ｓ）を使用して、このデータベースにおける配列全体の数を特定する。パラメータ−ｚおよび−ｓに関する値は、これらの値が別段提供されない場合は、サブセット化されたデータベースのサイズ全体に基づいて自動的に計算される。このデータベースはまた、このデータベースの対象（ｓｕｂｊｅｃｔ）の開始を示す第１の序数（ｏｒｄｉｎａｌ）ＩＤ（Ｘ）を特定することによって、そして、このデータベースの対象の終端を示す第２の序数ＩＤ（ｙ）を特定することによって、複数の下位区分に分割され得、ここで、上記第１の序数ＩＤは、０〜Ｎ−１の範囲に及び、ここで、Ｎは、データベース中の配列数である。このデータベースは、任意の適切なサイズの部分に細分され得る。例えば、このデータベースは、ノードにおけるＲＡＭに適合するように十分小さい部分に細分され得る。
【００３５】
複数のワードマッチ（ｗｏｒｄ ｍａｔｃｈｅ）の長さは、任意の方法を使用して、本発明の方法の工程（ｄ）において伸長され得る。例えば、この伸長工程は、以下の工程を包含し得る：（ｉ）１セットのハイスコアセグメントペアを評価して、第１の基準に従う上記セットにおいて最もスコアの高い鎖を決定する工程であって、ここで、この鎖は、ハイスコアセグメントペアにおける上記セットのサブセットを含む工程；（ｉｉ）ハイスコアセグメントペアの上記セットから上記の鎖を取り出す工程；および（ｉｉｉ）このハイスコアセグメントペアが無くなるまで、上記の工程（ｉ）および（ｉｉ）を反復する工程。好ましくは、この評価工程（ｉ）は、第２の基準に従って再計算を必要としないハイスコアセグメントペアの上記セットにおけるサブセットを決定する工程を包含する。別の例において、複数のワードマッチの長さは、ｌｉｎｋ＿ｈｓｐｓ（）を用いて伸長される。この複数のワードマッチの長さは、別個のプロセッサ上で伸長され得る。あるいは、この複数のワードマッチの長さは、データベース検索を実行するために使用される、同一のプロセッサ上で伸長され得る。
【００３６】
この複数のハイスコアセグメントペアは、任意の適切な方法を使用し、本発明の方法の工程（ｄ）にて結合され得る。例えば、複数のハイスコアセグメントペアは、「ｐｂｍｅｒｇｅ」プログラムを使用して結合され得る。
【００３７】
本発明の方法は、適切な配列ハードウェア上で実行され得る。例えば、本方法は、商用既製（「ＣＯＴＳ」）ハードウェア上で実行され得る。好ましくは、本方法は、Ｂｅｏｗｕｌｆ型並列処理アーキテクチャで実行され得る。
【００３８】
本方法は、任意の適切なデータベースにおいて、任意のクエリー配列について検索を実行するために使用され得るが、但し、このクエリー配列は、このデータベースに含まれる少なくともいくつかの配列と適合性である。しかし、いくつかの環境においては好ましいのであるが、このクエリー配列がこのデータベースに含まれる全ての配列と適合性である必要はない。例えば、あるタンパク質配列は、核酸配列とに加えて、タンパク質の配列を含むデータベースにおける検索を実行するのためのクエリー配列として使用され得る。同様に、核酸配列（例えば、ＤＮＡ配列またはＲＮＡ配列）は、タンパク質配列に加えて、核酸配列を含むデータベースにおける検索を実行するためのクエリー配列として使用され得る。
【００３９】
本発明の方法は、ゲノム配列、ｃＤＮＡ配列、ＥＳＴ配列またはそれらの組み合わせを含むデータベースのような任意の適切な配列データベースにおける検索を実行するために使用され得る。本発明の方法は、公開データベース（例えば、ＧｅｎＢａｎｋ）または加入者限定データベースにおける検索を実施するのに使用され得る。
【００４０】
別の特定の実施形態において、本発明は、以下の工程を使用するＢＬＡＳＴアルゴリズムを用いるデータベースにおける配列検索を実行するための方法に関する：（ａ）クエリー配列から長さｗのハイスコアワードのリストをコンパイルして；（ｂ）このデータベースにおける各配列のついて、閾値Ｔを超えるスコアを有するワードヒットについてスキャンし；そして（ｃ）各ワードヒットについて、このヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアセグメントペア（ＨＳＰ）を形成し、ここで、改良型は、以下の（ｉ）、（ｉｉ）、（ｉｉｉ）のうちの１つ以上を含む：（ｉ）上記検索を実行する前に、複数のクエリー配列を一体型クエリー配列に結合する工程；（ｉｉ）上記検索を実行する前に、データベースの複数の下位区分を決定する工程；（ｉｉｉ）可能な何時においても、ハッシュテーブルは、プロセッサとメモリとの間で往来するのではなく、プロセッサキャッシュに留まるようにコードを再構築する工程；および／または（ｉｖ）１メガ塩基（１００万塩基または１００万塩基対）以上のクエリー配列を、上記の検索を実行する前に、より小さい部分に分割する工程（例えば、上記クエリー配列を、重複する部分に分割し、その検索において別々に、各部分を実行することによる）。好ましくは、このクエリー配列は、以下の工程によってより小さい部分に分割される：ａ）上記クエリー配列を複数の重なり合う（オーバーラップ）配列へと分割する工程；ｂ）重なり合う部分の各々が、唯一の重なり合う配列においてのみ含まれるように、上記における複数の重なり合う配列から、重なり合う部分を取り除く工程；およびｃ）除去を受けた部分が、上記の重なり合う部分の全体に及ぶ任意のＨＳＰを含むか否かを検出する工程であって、そして、このようなＨＳＰが検出された場合に、上記ＨＳＰを生じるオリジナルヒットを見出し、そして分割されていないクエリー配列の状況におけるＨＳＰを伸長する工程。このクエリー配列は、任意の適切なサイズ（例えば、約１０キロ塩基（１０００塩基または１０００塩基対））のより小さい部分へと分割され得る。
【００４１】
さらに別の具体的な実施形態において、本発明は、データベースにおける配列検索を実行する為のシステムに関し、このシステムは、マネージャーノードおよび複数のワーカーノードを備え、ここで、上記マネージャーノードは、クライアントステーションおよび上記ワーカーノードの各々に作動可能に接続されて、そして、上記システムは、上記の方法のいずれか１つに従って、データベース中の配列検索を実行することが可能である。１つの例において、ハードウェアのレベルで、このマネージャーモジュールは、デュアルＣＰＵマザーボード、ＲＡＭ、ディスク、およびネットワークカードを備えるマネージャーノードを備える。他のノード（例えば、ワーカーノード）は、類似のハードウェア（通常は、ディスクは備えない）を備える。１つの好ましい例において、このマネージャノードは、マネージャー「デーモン」（恒久的プロセス（ｐｅｒｓｉｓｔｅｎｔ ｐｒｏｃｅｓｓ））ソフトウェアをこのマネージャーノード上で実行させるが、ワーカーデーモンは、ワーカーノード上で実行させる。このマネージャーデーモンは、クライアントプロセスからジョブリクエストを受信する工程を担い、このクライアントプロセスは代表的にはクライアントワークステーションにおいて実行され、そのジョブリクエストを待ち行列にいれ（ｑｕｅｕｉｎｇ）、そのジョブリクエストをサブジョブまたはタスクに分割し、これらのタスクのスケジュール管理を行い、そして、それらのタスクをワーカーデーモンへと割り当てることを担っている。このワーカーデーモンは、マネージャーデーモンからのサブジョブをリクエストし、そして、そのマネージャーデーモに結果を戻す。
【００４２】
これらの要素（エレメント）およびアルゴリズムの操作の詳細な説明は、以下に提供される。本明細書中で引用される全ての参考文献は、その全体が参考として援用される。
【００４３】
（発明の詳細な説明）
開示の明確化のためであって、かつ、限定のためではなく、本発明の詳細な説明は、以下に続く小節に分割される。
【００４４】
（定義）
別段定義されない限り、本明細書中で使用される、全ての専門用語および科学用語は、本明細書中において、本発明が属する分野の当業者によって通常理解されるものと同じ意味を有する。本明細書中で参照される、全ての、特許、特許出願、公開された特許出願、および他の刊行物は、それらの全体が参考として援用される。
【００４５】
本明細書中で使用される場合、「ａ」または「ａｎ」は、「少なくとも１つ」または、「１つ以上」を意味する。
【００４６】
本発明の目的について、別段示されない限り、「ＢＬＡＳＴ」とは、Ａｌｔｓｃｈｕｌら，Ｊ．Ｍｏｌ．Ｂｉｏｌ．，２１５： ４０３−４１０（１９９０）（これらの全体が、本明細書中で参考として援用される）に記載の「Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ」アルゴリズムに基づくアルゴリズムをいう。「ＮＣＢＩ ＢＬＡＳＴ」とは、ＢＬＡＳＴアルゴリズムのＮＣＢＩ（Ｎａｔｉｏｎａｌ Ｃｅｎｔｅｒ ｆｏｒ Ｂｉｏｔｅｃｈｎｏｌｏｇｙ Ｉｎｆｏｒｍａｔｉｏｎ）版の実装のバージョン２．１．２をいい、これは、当該分野で周知である。
【００４７】
本明細書中で使用される場合、「ノード」とは、計算ツリー（ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｒｅｅ）または計算システムにおける別個のスポット（点）または位置をいう。ノードは、ＣＰＵ、プロセッサもしくはマイクロプロセッサまたはそれらの機能部分、あるいはそれらの組み合わせであり得る。例えば、コンピューティングクラスタ（計算クラスタ）の状況において、ノードは、単一のコンピュータであり得、これは、１以上のプロセッサ（ＣＰＵ）および個々に共用された他のハードウェア（例えば、メモリ（ＲＡＭ）またはネットワークカードなど）からなる。
【００４８】
本明細書中で使用される場合、「ｌｉｎｋ＿ｈｓｐｓ」は、ＮＣＢＩ ｂｌａｓｔツールのサブルーチンをいう。各クエリー配列および各データベース配列について、このルーチンは、これらの２つの配列の間の、初期段階において計算されたＨＰＳを連結し、これらの２つの配列がどの程度類似しているかを評価する。ｌｉｎｋ＿ｈｓｐｓの結果に基づいて、このプログラムは、ギャップ付きアライメントがこれらの配列ペアについて計算されるか否かを決定する。
【００４９】
（クエリーパッキング）
ＢＬＡＳＴにおいて、配列データベースにおける各クエリーの検索は、その検索を設定するために、計算上のオーバーヘッドを要求する。具体的には、ルックアップテーブルが、このクエリーに対して構築されることが必要とされる。いくつかのクエリーを１つの検索に対して連結することによって、１クエリー当たりの計算上のオーバーヘッドの量が低減され、そして、クエリー処理における全体の処理量は増大される。１つの実施形態において、このＢＬＡＳＴアルゴリズムは、複数のクエリー配列を、このデータベースの単一のスキャニングパスへと圧縮（パッキング）し、従って、複数の小さいなクエリーに対する処理時間を低減するが、一方で、同一の入力用クエリーについてＮＣＢＩ ＢＬＡＳＴで生成された結果と同一の結果を生成するように改変される。具体的には、このクエリールックアップテーブルは、「クエリー番号」と称される必要な索引と共に、いくつかのクエリーに由来する情報を含むように改変され、それぞれのクエリーとその情報を連結する。
【００５０】
一体化型クエリーの結果が、それを構成するクエリーの個々の検索によって生成された結果と同一であることは重要である。同一の結果が生成されることを確認するために、各クエリーに対して序数を割り当てかつその序数をハッシュテーブルの記入項目に追加することによって、ハッシュテーブル生成が複数のクエリーに対するスキャニングと組み合わされる。さらに、全てのスキャン後の段階を実行するために、別個の検索構造体が、各クエリーに対して維持されており、そのスキャン後の段階としては、対角成分計算（例えば、ギャップのない伸長、ギャップ付伸長、およびアライメント）が挙げられる。
【００５１】
この実施形態において、長さパラメータは、どれほど多くのクエリーデータが結合され得るかを決定するために使用され得る。ＢＬＡＳＴの従来技術の実装においては、、メインループが、クエリーをインプットとして受信し、そして、イタレーション（反復）毎に１つのクエリーを処理していた。本実施形態において、このメインループは、一体型クエリーの全長が、長さパラメータに到達するか、またはそれを上回るまで、クエリーを結合する内部ループを有し、そしてデータベース検索をこの一体型クエリーを用いて実行するように改変されている。この一体型データベース検索の結果は、一体型クエリーの全てにおいて有意なワードマッチの全てを含む。次の工程は、ＨＳＰへとこれらのワードを伸長することを包含する。この工程の対角成分プロセシング（ｄｉａｇｏｎａｌ ｐｒｏｃｅｓｓｉｎｇ）は、クエリー特異的であり、そして、全ての対角成分計算は、この内部ループ内でクエリー毎に独立して実行される。
【００５２】
１つの好ましい実施形態において、クエリー配列Ｑの各々およびデータベース配列Ｄの各々にとって、本発明の方法は、以下の処理工程を実行する。
１．閾値を幾分上回る、ＱおよびＤの全てのローカルアライメントである、Ａ１（Ｑ，Ｄ），Ａ２（Ｑ，Ｄ）．．．，Ａｎ（Ｑ，Ｄ）を見つけ出す。
２．上位ｎのスコアの高いデータベース配列Ｄについて、全てのアライメントである、Ａ１（Ｑ，Ｄ），Ａ２（Ｑ，Ｄ）．．．，Ａｎ（Ｑ，Ｄ）を報告する。
【００５３】
このＢＬＡＳＴに特定のものは、その内部工程であり、つまりアライメントを見出す工程である。ＢＬＡＳＴヒューリスティックにとって重要であるのは、統計学的に有意なアライメントが、並置されたワードにおけるハイスコアペア（ＨＳＰ）を含むという可能性があるというこである。このアルゴリズムはまずはじめに、クエリー配列とデータ配列との間の短く正確なマッチ（デフォルトの長さは、ヌクレオチドに対しては、１１であり、タンパク質に対しては、３である）について検索する。このような一致は、ヒットと称される。次いで、これらのヒットは、はじめは、ギャップなしで伸長され、次いで、ギャップ付きで伸長され、そして、所定の閾値を越えるこれらのＨＳＰが戻される。完全な伸長工程は、計算的には非常に負荷のかかるものであり、そして、ＢＬＡＳＴは、統計的にＨＳＰである可能性が高いそれらのペアについて完全なアライメントを計算することのみにより、不必要な計算を実行することを回避する。
【００５４】
Ｐａｒａｃｅｌ ＢＬＡＳＴにおいて最適化されたこのアルゴリズムのうちの１つの部分は、は、ヒット生成が生じる方法である。ヒット生成のためのアルゴリズムは、以下である：
１．クエリーをプリプロセスし、以下のハッシュテーブルを生成する：
（ｎマー，ｎマーが存在するクエリーの位置）
２．このデータベース配列を検討し、そして、ｎマーの各々について、ハッシュテーブルにおけるそのｎマーを調べる。このテーブルのインディックスにおける任意の位置が、ヒットである。
【００５５】
例えば、このクエリーがＭＳＬＰＴであると仮定する。従って、この３マーが、１）ＭＳＬ、２）ＳＬＰ、および３）ＬＰＴである。このハッシュテーブルは、表１に示される。従って、ＳＬＰを含むデータベース配列は、例えば、クエリーの第２位におけるヒットを生成する。
【００５６】
【表１】
（表１ クエリーＭＳＬＰＴについてのハッシュテーブル）
アミノ酸の３マー（ＡＡＡ．．．ＹＹＹ）の各々について、このテーブルは、３マーが存在するクエリー内のそれらの位置についてのエントリーを含む。例えば、ＭＳＬは、第１位で現れる。
【００５７】
ＢＬＡＳＴアルゴリズムのうちで最も「費用のかかる」（メモリを消費する）データ構造の１つは、上述のハッシュテーブルである。非常に高いレベルで、このアルゴリズムは、以下のようである：
１．ハッシュテーブルを配置（ｐｏｐｕｌａｔｅ）する。
２．このハッシュテーブルにおけるヒットの各々に対して、さらなるプロセシングを実行する。
【００５８】
ＮＣＢＩ ＢＬＡＳＴコードは、このハッシュテーブルの任意の特別な管理をなんら行わない。Ｐａｒａｃｅｌ ＢＬＡＳＴは、このコードを再構築し、その結果、可能である何時においても、ハッシュテーブルが、プロセッサとメモリとの間を往来するのではなく、プロセッサのキャッシュにとどまる。このことは、このテーブル中の値をコードすることに幾分関連し、メモリの使用頻度および、従ってテーブルサイズを減少して、その結果、このテーブルは、そのキャッシュに対して最適化する。キャッシュアクセスは、メモリアクセスようりも有意に高速であるので、これは、実質的な速度の向上を生じる。
【００５９】
（動的データベース分割）
先行技術において、検索されるべき大規模データベースは、静的に、いくつかのより小さいデータベースに分割され得た。しかし、このような設定は、ＢＬＡＳＴ検索全体が、これらのより小さいデータベースの各々に関して実施されることを要求し、これらの従属的な検索における結果を結合する静的で効果的な方法は、存在しない。本発明の１つの実施形態において、このＢＬＡＳＴアルゴリズムは、単一の大規模データベースに対する検索を分割して、複数のより小さいデータベースがサブセットを表すように構築することによって、その単一のデータベースのサブセットに対する複数の検索へと分割することを支援するように改変される。この実施形態において、この結果は、自動的に再結合され、分割することなしにこのデータベース全体を検索することによって生成されたレポートと生物学的に等価である単一のＢＬＡＳＴレポートへを作成する。この改変された方法は、本明細書中で「動的データベース分割」と呼ばれ、以下の４つの領域において、その基礎的なＢＬＡＳＴアルゴリズムに対する改変を必要とする：第１に、この静的パラメータは、正確な部分的結果を生成するように調整される必要がある。第２に、このデータベースにアクセスするのに使用される入力／出力ルーチンは、このデータベースのサブセットへのアクセスをサポートするように改変される必要がある。第３に、中間結果のメモリイメージが、生成される必要がある。第４に、これらのメモリイメージが、適切に再結合され、単一のひとつになったＢＬＡＳＴレポート生成する必要がある。
【００６０】
ＢＬＡＳＴは、データベースのサイズおよびこのデータベースにおける配列数を使用して、このデータベースの検索によって生成された結果の統計学的な有意性を計算する。一貫した結果に到達するために、検索される、塩基におけるサイズおよびデータベース全体の配列数は、特定されなければならない。ＢＬＡＳＴの従来の実装は、コマンドライン引数（−ｚ）を提供して、静的な計算において使用されるデータベース全体の塩基のサイズを特定していたが、配列全体の数を特定するための対応する方法を提供していなかった。本発明の１つの実施形態において、新規のコマンドラインオプション（−ｓ）が、この番号を特定するために追加され、このオプションは、検索の間で、このコードによって参照される、このオプションのデータ構造に追加された。この実施形態において、静的パラメータを計算するコードは、このデータベース全体において含まれる実際の配列数によりはむしろ、この−ｓオプションの値を使用する。さらなる実施形態において、これらの−ｚおよび−ｓのパラメータの値は、別段提供されない限り、サブセット化されたデータベースのサイズ全体にもとづて自動的に計算される。
【００６１】
１つの実施形態おいて、このＢＬＡＳＴアルゴリズムは、データベースのサブセットを検索するように改変された。さらなる実施形態において、このデータベースのサブセットは、以下の命名法を使用して特定され得る：「ｄａｔａｂａｓｅ＃ｘ−ｙ」、ここで「ｄａｔａｂａｓｅ」は、データベース名であり、ｘは、検索において含まれる第１の序数ＩＤ（「ＯＩＤ」）であり、そして、ｙは、この検索において含まれる最後のＯＩＤである。この実施形態において、ＯＩＤは、０からＮ−１の範囲に及び、ここで、Ｎは、このデータベースにおける配列数である。なおさらなる実施形態において、このデータベースのサブセットは、以下の命名法を使用して、特定され得る：「ｄａｔａｂａｓｅ＃ｘ−ｙ＃ｎ」、ここで、ｎは、この特定されたサブセットにおける塩基数である。ｎが特定されないと、データベース全体のサイズが使用され、つまり、この数は、そのレポートにおけるサイズ情報にのみ影響する。
【００６２】
この実施形態において、ｒｅａｄｄｂサブルーチンにおけるメモリマップファイルの概念に基づき、ＮＣＢＩ ＢＬＡＳＴコードは、塩基変化を反映するように改変され得、このサブルーチンは、ｉｎｄｅｘｆｐファイル、ｈｅａｄｅｒｆｐファイル、およびｓｅｑｕｅｎｃｅｆｐファイルを、基礎的なｒｅａｄｄｂデータ構造体ＲｅａｄＤＢＦＩＬＥの中に含む。ＢＬＡＳＴの従来技術型の実装は、ｍｍａｐ（２）ＵＮＩＸ（登録商標）システムコールまたはその等価物を使用して（Ｎｌｍ＿ＭｅｍＭａｐＩｎｉｔを呼び出すことにより）ファイル全体がマップされることを可能にするのみであった。この実施形態において、ここでは、３つまでのファイルの範囲が、これらのインディクスファイル（索引ファイル）における、ヘッダー、配列、および多義性（ａｍｂｉｇｕｉｔｙ）のセクションについて、マップされることを可能にする。この実施形態において、インディックスファイルが、ｒｅａｄｄｂ＿ｎｅｗ＿ｉｎｔｅｎａｌにおいて読まれると、はじめは、これは、メモリマップを全く使用することなしに、最初にオープンされる。一旦、このファイル中の配列数が決定されると、このインディクスファイルは、クローズされ、そして、特定されたメモリマップについての、２つ（タンパク質）または３つ（ＤＮＡ）の範囲を用いてリオープンされる。ＯＩＤの範囲が使用されると、このヘッダーファイルおよび配列ファイルは、ｒｅａｄｄｂ＿ｎｅｗ＿ｉｎｔｅｎａｌによるＲｅａｄＤＢＦＩＬＥ構造体において計算され、そして記憶される。その後、それらは、それらがＲｅａｄＤＢＯｐｅｎＭＨｄｒＡｎｄＳｅｑＦｉｌｅｓでオープンされたときに、このファイルの範囲のみをマップするのに使用される。
【００６３】
１つの実施形態において、このＢＬＡＳＴアルゴリズムは、最終的なＢＬＡＳＴレポートのかわりに、出力として中間結果を生成するように改変される。この中間結果は、アライメントを生成する前の、ｂｌａｓｔａｌｌメインループにおける点において、動的データ構造体のメモリイメージの、順番に並べられたコピーである。この実施形態において、この点における動的データ構造体は、移動され、そして、各メモリブロックは、相対インディクスに対する絶対ＲＡＭアドレスから、記述されたメモリブロックへと変換される埋め込まれたポインタ（ｅｍｂｅｄｄｅｄ ｐｏｉｎｔｅｒ）情報にそって記憶される。この実施形態において、テキスト出力はこの段階においては生成されない。
【００６４】
この実施形態において、「ｐｂｍｅｒｇｅ」と呼ばれるプログラムが、上述のように、膨大なデータベースの複数の部分から中間的結果を読みとるために、そして、このメモリブロックのために動的メモリを割り当て、そして、埋め込まれたメモリレファレンスから、絶対ＲＡＭアドレスに対する相対インディクスに変換しも戻すことよって、それらを各々の等価なメモリイメージへと記述するために、書かれた。次いで、ｐｂｍｅｒｇｅプログラムは、複数の中間結果を、結果の単一のセットへと結合して、この結合した結果をスコアによってソートし、もっとスコアの低いアライメントを破棄し、リクエストされた数の最良のマッチを生じる。最終的に、ｐｂｍｅｒｇｅは、単一の結合されたＢＬＡＳＴレポートを出力として生成するために、上記のように、短く巡回する、ｂｌａｓｔａｌｌメインループの後端部分を実行する。
【００６５】
（ハイスコアセグメントペアを連結する工程）
発明の背景で説明したように、実験的証拠によって、ＢＬＡＳＴにおける計算時間の大半は、ヒットを伸長することによって、そして、特に、ギャップ付きの伸長を実施する場合に費やされることが実証されている。代表的な実装において、この工程は、ｌｉｎｋ＿ｈｓｐｓ（）と命名された関数によって行われる。発明の背景において説明した改良型をもってしても、ＢＬＡＳＴの計算時間の有意な量が、なおも、ｌｉｎｋ＿ｈｓｐｓ（）において費やされている。この関数およびｌｉｎｋ＿ｈｓｐｓ（）のコンテキストは、以下に説明される：クエリー配列およびデータベースが与えられると、このデータベース中の配列Ｓの各々について、ＨＳＰのセットＨをこの配列Ｓについて決定する。次いで、ｌｎｋ＿ｈｓｐｓ（）関数は、この配列ＳについてのＨＳＰのセットＨの統計学的有意性を推定し、統計学的有意性が予め決定された閾値を超えるとき、最も有意性のあるマッチのリストに配列Ｓを加える。一旦、これらの配列の全てが処理されると、ＢＬＡＳＴは、最も有意性のあるマッチにおいてギャップ付き伸長を実施し、そして、そのアライメントを出力する。
【００６６】
より詳細には、ｌｉｎｋ＿ｈｓｐｓ（）は、以下のアルゴリズムを実装する：（１）ＨＳＰのセットＨから最もスコアの高い鎖Ｃを探し出し；（２）このＣについての有意性を計算し；（３）ＨからＣを取り除き；そして（４）Ｈが無くなるまで反復する。鎖Ｃについてのスコアは、以下のように計算される：ｋ個のＨＳＰの順列Ｈ１，Ｈ２，．．．，Ｈｋからなり、ここで、Ｈｉは、Ｈｉ＋１よりも前であり、従って：
【００６７】
【数１】
である。ここで、ｓｃｏｒｅ（Ｈｉ）は、そのＨＳＰのスコアであって、ｃｏｎｎｅｃｔ（Ｈｉ，Ｈｉ＋１）は、２つのＨＳＰを結合するためのペナルティである。最大スコア鎖Ｃの計算は、以下の観察に基づく計算学的有効な様式で実施され得る：Ｓ（Ｈ）を、ＨＳＰ Ｈで終止する最も高いスコアの鎖とする。その結果として、この鎖において、Ｈは、先行する全てのＨ’のセットについて、
【００６８】
【数２】
である。換言すると、Ｈで終止する鎖における最も高いスコアは、（その先行する部分のスコアにおける最大値）−（これらのそれぞれの結合ペナルティ）である。その結果として、全てのＳ（ｈ）の値が、既に計算されていると、Ｓ（Ｈ）は、容易に計算されるということである。一般に、ｋ個のＨＳＰ Ｈの鎖について、Ｈに先立つ Ｏ（ｋ）ＨＳＰが存在し得る。この依存性は、図１において例示される。図１において、各ノードは、ＨＳＰを表す。鎖は、有向エッジ（ｄｉｒｅｃｔｅｄ ｅｄｇｅ）によって接続されるノードのセットである。ノードＡが取り除かれるとき、ノードＸは再計算される必要がある。しかし、ＣまたはＤで終止する最良の鎖は変化せず、Ｓ（Ｃ）およびＳ（Ｄ）は、ノードＡが取り除かれたときに再計算される必要がない。
【００６９】
現在、ＢＬＡＳＴの代表的な実装は、大規模ギャップ生成（ｌａｒｇｅ ｇａｐ ｃｒｉｔｅｒｉｏｎ）および小規模ギャップ生成（ｓｍａｌｌ ｇａｐ ｃｒｉｔｅｒｉｏｎ）として知られている、２つの結合関数を使用する。大規模ギャップ生成によって、おおきなギャップが形成され得、そして、この結合ペナルティをゼロ（０）に設定する。小規模ギャプ生成によって、予め決定されている定数Ａを超えるギャップは許容されない。小規模ギャップ生成は、Ａ以下のギャップについて、そのペナルティを０に設定し、Ａを超えるギャップについて負の無限大であるとする。現行の実装は、Ｓ（ｈ）の各々を計算するのに時間Ｏ（ｋ）を必要とし、そして、Ｈで終る最高スコア鎖を見出すために時間Ｏ（ｋ２）を必要とする。全ての鎖を見出すには、時間Ｏ（ｋ３）がかかる。ｋがクエリー長に対して線形的に増大し、そして、ＢＬＡＳＴアルゴリズムの残りのものは、固定されたデータベースについて、クエリー長対して線形的に増大するので、ｌｉｎｋ＿ｈｓｐｓ（）は長いクエリー配列においては実行時間のボトルネックになる。この適用において他で議論されるように、本発明の１つの実施形態は、「クエリーパッキング」を使用し、この「クエリーパッキング」はいくつかのクエリーを鎖状に繋いだものを含み、従って、クエリー長を増大させる。実験的証拠は、１Ｍｂクエリーについて、計算時間の８０％までが、ｌｉｎｋ＿ｈｓｐｓ（）関数を実行することに費やされ得ることを実証している。ＨＳＰのセットＨにおいて、同一の開始要素（エレメント）を有するエレメントは、同じクラスの属している称される。上述のように、ｌｉｎｋ＿ｈｓｐｓ（）の１つの工程は、最も高いスコアの鎖Ｃを、ＨＳＰのセットＨから取り出すことである。鎖のスコアを計算することは、この鎖における先行する点に依存する様式で、実行されるので、上述したように、ＨからＣを取り出すことは、Ｈが存続している全てのＣ依存的なエレメントが再計算されることを要求している。定義によると、鎖における全てのＨＳＰは、同じクラスに属している。鎖が取り除かれると、このクラスの全ての残りのエレメントは、再計算されることが必要とされる。２つの別個のギャップ基準を使用するＢＬＡＳＴの１つの実装において、Ｈにおける各エレメントは、別個の２つのクラスに属してており；１つの基準に対して最良の鎖は、別の基準における異なるクラスからのエレメントを含み得る。現行の実装において、１つの基準における最良の鎖を取り出すことは、全てのクラスの他の基準が再計算されることを必要とする。本発明の１つの実施形態において、ｌｉｎｋ＿ｈｓｐｓ（）の性能は、この種類の再計算を避けることよって改善される。
【００７０】
ＨＳＰのセットＨ、２つのギャップ基準、およびＨにおけるエレメント（要素）ｈが与えらると、ｌｉｎｋ１（ｈ）は、基準１に従った最も高いスコアの鎖におけるｈに対するその前のＨＳＰであり、そして、ｌｉｎｋ２（ｈ）は、基準２に従った最も高いスコアの鎖におけるｈに対するその前のＨＳＰであることを意味する。フォレスト（ｆｏｒｅｓｔ）Ｆ１は、それらの親（ペアレント）にように、ｌｉｎｋ１（ｈ）を有するサブツリーのセットとして定義される。同様にして、フォレストＦ２は、それらの親（ペアレント）として、ｌｉｎｋ２（ｈ）を有するサブツリーのセットとして定義される。一般に、Ｆ１におけるエレメント（要素）ｈが取り除かれると、ｈにおいてルートを有する部分ツリー（サブツリー）におけるＨＳＰのみが、変化される必要がある。同様に、Ｆ１におけるエレメント（要素）ｈが取り除かれると、定義によれば、その鎖の中の全てのＨＳＰは、Ｆ１の１つのツリーの中にある。ｈにおいてルートを有する部分ツリー（サブツリー）におけるＨＳＰのみが、変化される必要があり；また、そのツリーのルートがまた取り除かれるので、そのツリーにおける残りのＨＳＰは、再計算される必要がある。しかし、再計算が必要なＨＳＰのセットは、必ずしも、Ｆ２について同じツリーにあるわけではない。本発明の１つの実施形態において、鎖全体が１度に全て取り除かれる代わりに、取り除かれる鎖の個々のエレメント（要素）は、個々に取り除かれ、同様にして、このエレメントのサブツリーも取り除かれる。
【００７１】
再計算の後に、ｌｉｎｋ＿ｈｓｐｓ（）は、新しいツリー構造における最良の鎖を決定する。このプロセスに対する愚直なアプローチは、ツリーが変化したＨＳＰの全てにアクセスすることが絡むということである。実験的な証拠によると、再計算を必要とするＨＳＰの数は変化したＨＳＰのわずかな部分であるという傾向があるので、このアプローチは、不必要に時間を消費することとなる。より効率的なアプローチでは、各ＨＳＰについてのスコアＳ（ｈ）に基づき、フォレストにおける各ツリーについてヒープ使用する。このヒープによって、このツリーの最もスコアの高い鎖が、Ｏ（１）時間内に決定されることを可能にする。再計算を必要とするＨＳＰのみがアクセスされるので、この総実行時間は、最も悪い場合で、Ｏ（ｒｍ０．５＋ｒｌｏｇｍ）であり、そして、実際には、Ｏ（ｒｌｏｇｍ）であり、ここで、ｒは、再計算の数であり、ｍは、ＨＳＰの数である。実験的な証拠によって、ｒは、実際には、ほぼｍ１．５である。
【００７２】
１つの例において、１．１Ｍｂのクエリーを、６５０Ｍｂの配列データベースに対して実行した。（米国の）全国バイオテクノロジー情報センター（「ＮＣＢＩ」）から利用可能であるＢＬＡＳＴの実装（バージョン２．１．２）は、実行に１７時間を必要とした。対照的に、上述のようなｌｉｎｋ＿ｈｓｐｓ（）の改良型を使用したＢＬＡＳＴの実装は、同じ条件のもと３時間未満で完了した。
【００７３】
上述したように、ハッシュテーブルにおける操作（ハッシュテーブルへの配置およびその繰り返し（ｌｏｏｐｉｎｇ ｏｖｅｒ ｉｔ）は、かなりの量の時間を費やす。これは、短いクエリーについては、特に、そのとおりであり、テーブルにおける僅かなエントリーのみが配置される。実際のところ、ＭｅｇａＢｌａｓｔが多くの小さなクエリーに関してヌクレオチド対ヌクレオチドの検索をより速く提供するように開発された１つの理由は、Ｚｈａｎｇ，Ｚ．，Ｓｃｈｗａｒｔｚ，Ｓ．，Ｗａｇｎｅｒ，Ｌ．ａｎｄ Ｍｉｌｌｅｒ，Ｗ．，Ａ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｌｉｇｎｉｎｇ ＤＮＡ ｓｅｑｕｅｎｃｅｓ．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ，７（１−２）：２０３−２１４（２０００）（これらの全体は、本明細書において、参考として援用される）に記載されている。例えば、以下のようなウェブ上で利用可能ないくつかのスクリプトがまた存在する：クエリーを一緒に「パック」するスクリプト、例えば、クエリーと間で「留意しない」処理を付す（すなわち、ヌクレオチドについては、Ｎ、アミノ酸についてはＸ）スクリプト、単一の検索を実行して、得られた結果に後処理を行い、一体型クエリー内でオリジナルクエリーのオフセットに対して修正を加えるスクリプト。例えば、クエリーＡＣＴＧおよびＧＣＧＣＧが、ＡＣＴＧＮＮＮＮＮＮＮＮＮＧＣＧＣＧとしてパックされ得る。留意しない点は、このクエリーに亘ってヒットが生じる可能性がないとすることである。ＭｅｇａＢｌａｓｔおよびこれらのスクリプトにかかわる問題点は、精度（ａｃｃｕｒａｃｙ）が失われるといことであり、すなわち、その統計値は、単一の長いクエリーと多くの短いクエリーについて相違意味するということである。
【００７４】
１つの好ましい実施形態に従って、Ｐａｒａｃｅｌ ＢＬＡＳＴ Ｑｕｅｒｙ Ｐａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍは、速度の向上を伴って統計学的な妥当性を維持する。１つの実施形態において、このＰａｒａｃｅｌ ＢＬＡＳＴ Ｑｕｅｒｙ Ｐａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍは、同じ時間において複数のクエリーのハッシュを構築することによって動作する。位置のみを含むハッシュテーブルの代わりに、これは、（クエリー番号，クエリーにおける位置）という順列ペアを含む。例えば、表１は、クエリーＱ１（ここで、Ｑ１＝ＭＳＬＰＴ）がハッシュされたときに生成されたハッシュテーブルを含む。さらに仮定したときに、クエリーＱ２＝ＡＬＰＴＶおよびＱ３＝ＶＭＳＬＩＣがハッシュされる。この得られたハッシュテーブルは、表２で示される。
【００７５】
（表２−クエリーＭＳＬＰＴ、ＡＬＰＴＶ、およびＶＭＳＬＩＣに対するクエリーパッキングハッシュテーブル）
【００７６】
【表２】
この最適化は、このハッシュテーブルが配置される方法、およびヒットがハッシュテーブルから読み出される方法に対する改変を含み、ヒットにおける全てのそれに続く処理は、同一のままである。重要なのは、いくつかのクエリーのパックされたパイプラインからのデータを用いてこのハッシュテーブルに十分に配置し、その結果、このハッシュテーブルは、過剰なることなく相対的に満たされている。これによって、少数のクエリーセットの効率を、有意に、改善する。ＭｅｇａＢｌａｓｔとは違って、この技術は、ヌクレオチドに加えて、アミノ酸のついても機能し、Ｐａｒａｃｅｌ ＢＬＡＳＴは、全ての改良型ＢＬＡＳＴについて統計学的に正確に、より高速検索を実行し得る。
【００７７】
（並列アーキテクチャにおける実装）
１つの実施形態において、上述のような改良を組み込んだＢＬＡＳＴアルゴリズムの実装は、Ｂｅｏｗｕｌｆ型並列処理アーキテクチャ上で実行される。この実施形態において、このマシンは、データベース検索を高速度のスループットで実行する。クエリーが受信されると、クエリーは、一体型クエリーサイズが予め決定された閾値に到達するまで、一体型クエリーへとパッキングされる。検索されるデータベースは、分割され、そして、このマシン上のプロセッサの各々は、このデータベースの特定の分割された部分についての一体型クエリー検索を取り扱う。好ましい実施形態において、このデータベースは、動的に分割され、各プロセッサは、ほぼ同じ時間の量での検索を完了する。各データベース検索の出力は、一体型クエリーにおいて、ヒットの各々とそのクエリーとを連結する情報にとともに、複数のヒットを含む。ヒットの各々についての対角成分計算は、クエリー特異的であるので、各クエリーのヒットは、ｌｉｎｋ＿ｈｓｐｓ（）を使用して別個に伸長される。１つの実施形態において、各クエリーのヒットは、別個のプロセッサー上で処理され得る。代替的な実施形態において、各クエリーのヒットは、このデータベース検索を実施するために使用される同一のプロセッサ上で伸長される。データベースの分割のために、全ての一体型クエリーのヒットが、見出され、そして、伸長されたとき、分割の中間結果が記憶される。最後には、全てのデータベース分割についての中間結果は、再結合されて、そして、最終的なＢＬＡＳＴレポートがこの一体型クエリーにおける各クエリーについて生成される。１つの好ましい実施形態において、このＢｌａｓｔＭａｃｈｉｎｅは、Ｂｅｏｗｕｌｆ型Ｌｉｎｕｘクラスターであり、マネージャーノードおよび複数のワーカーノードからなる（図２を参照のこと）。各ノードは、Ｐａｒａｃｅｌ ＢＬＡＳＴ、すなわち、最適化したバージョンのＮＣＢＩ ＢＬＡＳＴを実行する。このマネージャーは、ジョブを分割してより小さな部分にし、それらの部分をワーカーに割り当て、それらの結果を回収し、そしてそれらの結果をクライアントに戻すことによって、クライアントＢＬＡＳＴリクエストに応答する。このシステムの多くの困難は、以下にさらに詳細に議論されているような局面（ａｓｐｅｃｔ）を、分割およびスケジュール管理することにある。わずか１個のＣＰＵを有するＢｌａｓｔＭａｃｈｉｎｅｓおよび９２個ものＣＰＵを有するＢｌａｓｔＭａｃｈｉｎｅｓが構築された。１つの実施形態において、各ワーカーノードは、２ＣＰＵ Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩシステムである。
【００７８】
ジョブを分散させるときの、２つの性能に関連する問題は、１）負荷分散（ｌｏａｄ ｂａｌａｎｃｉｎｇ）および２）キャッシングである。負荷分散を例示するために、単一のプロセッサで１００分かかるジョブを５０プロセッサに分散することを仮定する。各プロセッサの負荷が同等であるとすると、これらのジョブは、２分間かかる。あるいは、４９のプロセッサが１分間を必要とする部分を受け取るとすると、最後のプロセッサが５１分間を必要とする部分を受け取る。次いで、問題全体が、５１分間かかるとすると、１つのＣＰＵにおいて必要とされる時間は、大まかに半分である。乏しい負荷分散のために、このジョブが、どんな方法でも、プロセッサの数だけに基いて期待される、５０倍近くの速度向上に到達し得ない。この種の異常な実情を改善するために、ジョブを可能な限り多くの部分に分割することが所望される。どの部分が最も時間を費やすかということを、先見的に知ることはできない（この時間の多くの部分が、ヒットの数に依存し、これは、検索を実行することなしには、知ることはできない）ので，より多くの部分に分割することによって、より速い部分がずっと速く完了することが可能され、従って、これらのプロセッサーは、残りの部分のために使用され得る。小部分の限界において、１つのジョブをこのような小部分へと分解して、それによって、プロセッサの数と同等の実際の速度向上を達成し得ることが望まれている。しかし、実際のところ、各部分に関連する、幾分少量のオーバーヘッドが存在し、そして、この分割がどれ程まで細かい単位であり得るかということに関しては限界が存在する。
【００７９】
直接的なクエリー分割技術は、各クエリーを、その別個のサブジョブに分割することである。ついで、このような部分の各々は、ＢＬＡＳＴアルゴリズムにおいてそれに続く工程で統計値を調整することを必要とせず、独立してスケジュール管理され、そして、異なるプロセッサーに配置され得る。各クエリー部分を独立してスケジュール管理する工程は、正確だが、最適ではないことがわかった。なぜならば、これが、上記のクエリーパッキングアルゴリズムによって提供される最適化したものを損なうためである。そのアルゴリズムは、いかに複数のクエリーが一緒にパックされ得ようとも、速度向上を達成する。そして、Ｐａｒａｃｅｌ Ｂｌａｓｔマネージャーノードは、いくつかの分散工程（ｂａｌａｎｃｉｎｇ）を実行し、一方で、そのマネージャーノードは、可能な限り細かく分割することを必要とし、より良好な付加分散を達成し、そして、より効率的な並列処理（ｐａｒａｌｌｅｌｉｓｍ）を使用し；他方で、そのマネージャーノードは、複数のクエリー配列を一緒に維持して、各部分における速度を最適化することを必要とする。待ち時間またはスループットについての重要性に依存して、かつ含まれるデータの特異性（ｓｐｅｃｉｆｉｃｓ）に依存して、異なったストラテジーが使用され得る。これらのストラテジーは、以下に詳細に議論されている。
【００８０】
上記で議論したように、Ｐａｒａｃｅｌ Ｂｌａｓｔがクエリーを分割するのと同じ方法で、これは、データベースを分割し得る。１つの実施形態において、各データベースＤおよび各クエリーＱについて、このＰａｒａｃｅｌ ＢＬＡＳＴアルゴリズムによって、ＱとＤとの間のアライメントが見出される。しかし、問題点が存在する。アライメントを見出すために、そのデータベース全体における、サイズおよび配列数に依存する統計学的なカットオフが、使用される。１つの実施形態において、強化されたＢＬＡＳＴコードは、プロセスマネージャーアルゴリズムがその情報を各クエリー部分に渡すことを可能にする。アルゴリズムの第２の部分は、同じクエリー部分に対応する全てのデータベース部分を一緒にする。クエリーＱの各々について、このアルゴリズムは、以下で詳細が説明されるように、ＭＥＲＧＥ（Ｄ１，Ｄ２，．．．，Ｄｍ）と呼ばれる関数にある上位ｎのデータベース配列を報告する。不運なことに、この一緒にする工程は、ネイティブＮＣＢＩ ＢＬＡＳＴの順位とは異なる順位を、時折生成し得え、これは、同じスコアを有するアライメントが、決定論的に（ｄｅｔｅｒｍｉｎｉｓｔｉｃａｌｌｙ）ソートされないためである。しかし、結果の質は、同等であり、これは、統計学的に有効なものである。
【００８１】
１つの実施形態において、マージ手順（合わせる手順）は、以下の通りである：データベース部分Ｄ１、Ｄ２、．．．、Ｄｍ、および各データベースについての上位ｎ個のアライメントを与え、全体として、上位ｎ個のアライメントを見つけ出す。好ましい実施形態において、クエリー分割およびデーターベース分割は、相互に独立しているので、両方の最適化は、同時に適用され得る。
【００８２】
データーベース分割の１つの利点は、データベースが、そのノード上のＲＡＭに適合するのに十分な小さい部分に分割され得ることである。これは、以下の２つの利点を提供する：
１．ＢＬＡＳＴアルゴリズムは、データベースが、ディスクからまたはネットワークを超えてデータベースにアクセスするよりもむしろメモリー内にとどまり得る場合に有意により速い様な様式で、コードされ、そして
２．データベース（特に、大規模なもの）を移動し回ることは、コストがかかるので、マネージャーは、同じデータベース部分を同じプロセッサに割り当てるように試み、それによって、有意な速度改善を達成する。
【００８３】
データベースキャッシュ処理もまた、優れた直線的スピードアップを可能にする。基本的に、（メモリーに実装するには大き過ぎるので）ディスクからデータベースをロードしなければならないジョブは、部分に分けられ得、ここで、各部分は、メモリーに実装するために十分に小さい。単一ＣＰＵについての合計時間は、（ＤＢディスクアクセス）＋（計算）となる。Ｎ個のＣＰＵについて、総時間は、１／Ｎ（ＤＢ ＲＡＭアクセス）＋（１／Ｎ）・（計算）になる。ＲＡＭアクセスがディスクアクセスよりずっと速いので、Ｎ個のＣＰＵに対する合計時間は、１つのＣＰＵに対についての時間の１／Ｎ未満であり、おそらくはそれよりずっと少なく、そして速度向上は、超直線的（ｓｕｐｅｒ−ｌｉｎｅａｒ）であり得る。
【００８４】
この効果は、多くの部分に分けられる大きなジョブについて特に著しく、すなわち、第１の部分が、プロセッサの数によってナイーブに（ｎａｉｖｅｌｙ）分割することに基づいたときに予期される速度と同じ速度で実行する。それに引き続く部分は、キャッシュされたデータベースを使用し得、そして、ずっと高速である。従って、全体のジョブ（より長いジョブについて）は、ディスクアクセス時間ではなく、ＲＡＭアクセス時間に向かう傾向がある。これは、ただ、Ｐａｒａｃｅｌ Ｂｌａｓｔマネージャーが同じデータベースを使用する異なるサブジョブを同じプロセッサに割り当てることを試みるので、生じることに注意のこと。
【００８５】
上記分割アルゴリズムが１セットのクエリー配列、または一体型クエリー、および複数の配列を含むデータベースに適用することが理解される。個々の配列は、代表的には、分割されない。しかし、利用可能なゲノム配列を用いて、個々の配列は、多くのメガ塩基長であり得る。１つの実施形態において、このような長い個々の配列を操作するために、Ｐａｒａｃｅｌ Ｂｌａｓｔは、クエリーチョッピング（Ｑｕｅｒｙ Ｃｈｏｐｐｉｎｇ）と呼ばれるアルゴリズムを使用する。
【００８６】
クエリーチョッピングを行うためのナイーブな方法は、長い配列を重なる部分に手動で分割し、そして図３に示されるように別々に各部分を実行する。これは、ＢＬＡＳＴの内部へのアクセスなしで、スクリプトによってなされることさえあり得る。Ｐａｒａｃｅｌ Ｂｌａｓｔのクエリーチョッピングは、重なりゾーンにおけるいくつかの潜在的な問題を正す点で、幾分より精巧である。
【００８７】
図４を参照して、全てのＨＳＰが生成された後、以下の３種類が存在する：重なり合わない領域に完全に含まれるＨＳＰ（ＨＳＰ１）、重なり合う部分に完全に含まれるＨＳＰ（ＨＳＰ２）、および重なり会う部分に部分的に含まれかつ重なり会わない部分に部分的に含まれるＨＳＰ（ＨＳＰ３およびＨＳＰ４）。第１のクラスのＨＳＰは、問題を呈しない。第２のクラスは、２回（左部分にて１回、右部分にて１回）見出される。それらを１回報告するのみという問題以外に、それらは、特別な問題を呈しない。第３のクラスは、少々厄介な問題である。
【００８８】
他の全てに優先する設計上の目標は、チョッピングがなく、そして配列全体が全体として処理された場合に得られる結果と同じ結果を提供することである。図４に示されるように、一部重なりを有するが隣接する部分のなかで十分短く停止する任意のアライメント（例えば、ＨＳＰ３）は、チョッピングが生じなかった場合に、その部分を十分に短く停止する。唯一の問題は、全体の重なりを含むまともなＨＳＰ（例えば、ＨＳＰ４）である。このような（まれな）ＨＳＰは、チョッピングによって中断されるが、重なりの両端（実際には、特定の縁効果が存在するので、重なりのいくらかの距離内にある）でヒットするチョップされた配列において、ＨＳＰとして検出され得る。
【００８９】
Ｐａｒａｃｅｌ ＢＬＡＳＴクエリーチョッピングアルゴリズムは、このようなＨＳＰを検出し、そしてそのＨＳＰに導く元のヒットに戻る。元のヒットは、チョップされないクエリーの状況でＨＳＰに拡張される。この操作はコストがかかるが、これが非常にまれである（重なりに完全にわたるＨＳＰが存在する場合にのみ存在する）ことを注意のこと。１つの好ましい実施形態において、Ｐａｒａｃｅｌ ＢＬＡＳＴは、１０キロ塩基のデフォルトの重なりを使用し、そこで再計算するための時間は、代表的に、クエリーをより忠実に分割し、そしてそれを複数のプロセッサに請け負わせ得ることによって得られる節約と比較して、非常に短い。
【００９０】
本発明の１つの実施形態において、Ｐａｒａｃｅｌ ＢＬＡＳＴは、マネージャーモジュールを含み、これは、ジョブを部分に分割し、各部分を最も利用可能なワーカー（例えば、プロセッサまたはＣＰＵ）に請け負わせ、次いで、部分を再結合する。このマネージメント機能を実行する際に、マネージャーモジュールは、特定の競合する束縛を考慮する。負荷分散の理由のため、できるだけ多くの部分に分割することが最適である。クエリーチョッピングおよびデータベース分割（マージ工程（あわせる工程）を有する）について、過剰な分割は、より多くのマージ（合わせること）を必要とし、従って、非能率的である。クエリー分割について、過剰な分割は、クエリーパッキングによって得られる効率を台無しにする。分割はまた、マシンの数を考慮すべきである。あまりにも少なすぎる部分への分割は、マシンをアイドリングさせ、一方、過剰の分割（マシンよりも多い部分への分割）は、負荷分散を改善することが望ましくあり得る。さらに、ディスクからネットワークを越えて、ワーカーのプロセッサにデータを移動する問題が存在する。十分に大きなデータベースについて、データの移動時間は、有意であり、計算時間を支配し得る。このような場合において、より少ない部分に分割することがより良好であり得る。Ｐａｒａｃｅｌ ＢＬＡＳＴは、これらのスケジューリング問題を扱う良好な（しかし、完全ではない）ジョブを実行するための１セットのヒューリスティックスを使用する。
【００９１】
（実験結果）
上記改善は、独立にまたは集団的に観察され得る。以下に考察される実施例において、全てのＢｌａｓｔＭａｃｈｉｎｅノードは、他の特に述べない限り、２ＧＢのＲＡＭを有する、９３３ＭＨｚで実行するデュアル Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩプロセッサからなった。
【００９２】
（コード最適化、ハッシュテーブルキャッシング、およびクエリーパッキング）
コード最適化の能力を実証するために、データ構造最適化、およびクエリーパッキング、ヒト第２２染色体から取得した５０，０００の２５マー（すなわち、合計１，２５０，０００塩基）のクエリーデータセットを、ＮＣＢＩ（１０，２３９配列、２４，３００，７７４塩基）からのヒト参照配列データベースに対して、実行した。９３３ＭＨｚにおいて実行する１つのＣＰＵ Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩシステムにおいて、ＮＣＢＩ ＢＬＡＳＴは、３時間１６分かかった。同じハードウェアにおいて、Ｐａｒａｃｅｌ ＢＬＡＳＴは、２２分３５秒かかった（８．７倍の速度向上）。
【００９３】
（クエリー分割）
クエリー分割、それ自体は、待ち時間を改善し、スループットを改善しない。しかし、以下に考察されるシステムのベンチマークの全てにおいてある役割を果たす。
【００９４】
（データベース分割）
Ｂａｙｌｏｒからのヒト転写データベースの８分の１（５．６メガ塩基を含む１０，６１０配列）を、ヒトアンサンブルデータベース（４．４ギガ塩基を含む３０，４４５配列）に対して実行した。この検索は、実質的な量のメモリーを必要とした。実際、ＮＣＢＩ ＢＬＡＳＴ２．１．２を、単一のＣＰＵ Ｐｅｎｔｉｕｍ（登録商標）ＩＩＩシステムランのメモリーのアウトで実行し、そして２週間後、失敗する。大規模メモリーにおいて、４ＣＰＵ Ａｌｐｈａ ＥＳ４０システム、ＮＣＢＩ ＢＬＡＳＴ２．１．２は、２１４時間１４分（ほぼ９日）で実行する。３２ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅでは、同じ検索は、たった３時間１７分で完了までで実行する。
【００９５】
（クエリーチョッピング）
クエリーチョッピングの能力を説明するために、全てのヒトＥＳＴを、第２２染色体に対して並置させた。使用されるたＥＳＴデータベースは、３７０万の配列を含み、合計１．８ギガ塩基である。第２２染色体（Ｓａｎｇｅｒ Ｃｅｎｔｒｅから入手される）は、３４．６メガ塩基の単一の配列を含む。このサイズの問題は、代表的なＬｉｎｕｘ ＰＣでのＮＣＢＩ ＢＬＡＳＴで実行され得ない（これは、すぐにメモリーをランアウトし、終わる）。Ｐａｒａｃｅｌ ＢＬＡＳＴのクエリーチョッピングを使用して、検索は、１９分４３秒で、８ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅで実行された。
【００９６】
（Ｃ．ｅｌｅｇａｎｓタンパク質 対 ＮＲ）
目的のいくつかの問題は、従来のコンピューターでの合理的な時間で完了され得ない。例えば、Ｗｏｒｍｐｅｐ１９データベース（Ｃ．ｅｌｅｇａｎｓからの８３０万ペプチドを含む１９，１０５配列を含む）を、ＮＲデータベース（ＮＣＢＩからの非冗長タンパク質配列データベース）に対して検索した。ＮＲは、１億８３００万のペプチドを含む５８２，２９０配列を含む。Ｗｏｒｍｐｅｐ配列のうちの１つが単一の２５，０００ペプチドタンパク質であることが特に注記される。１ＣＰＵシステムにおいて、ＮＣＢＩ ＢＬＡＳＴは、４日後に失敗した（おそらく、配列サイズに関連するメモリー問題に起因する）。Ｐａｒａｃｅｌ ＢＬＡＳＴを用いる３２ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅにおいて、同じ検索は、１時間５７分で完了まで実行した。
【００９７】
（全てのヒトＥＳＴ 対 全ての染色体）
現在までの最も大きな検索実行のうちの１つは、全てのヒトＥＳＴと全てのヒト染色体とのアライメントであった。上記のように、使用されたＥＳＴデータベースは、３７０万配列を含み、合計１．８ギガベースである。完全なセットのヒト染色体（ＵＣＳＣから得られる）は、３，６２６配列を含み、合計３．３ギガベースである。この検索は、クエリーチョッピングなしでは可能でなく、そして上で網羅される他の最適化の全てなしでは、過度に遅い。４８ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅでのＰａｒａｃｅｌ ＢＬＡＳＴを用いて、８５時間４９分で完了まで実行された。現在、ＥＳＴおよび第２２染色体を用いて実施されるような、本発明者らが、結果を詳細に分析し得るのに十分な、ヒト染色体の大部分の注釈が存在していない。
【００９８】
（結論）
Ｐａｒａｃｅｌ ＢｌａｓｔＭａｃｈｉｎｅは、ゲノムスケールでの相同性検索のためのシステムである。相同性検索の感度および選択性を改善することに焦点を当てるよりもむしろ、以前に可能であったよりも速くそしてより大きなデータについての合理的に良好なジョブをすることを求める。Ｐａｒａｃｅｌ ＢＬＡＳＴは、問題を分割し、そしてできるだけ多くのノードにそれらを請け負わせる、多くの個々の最適化を組み合わせる。各ノードは、ＣＰＵをより効率的に使用するように最適化されたコードを実行する。クエリー分割、データベース分割、クエリーチョッピング、クエリーパッキング、データベースキャッシュ処理、ハッシュテーブルキャッシュ処理、およびアセンブリ最適化の組合せによって、ＢｌａｓｔＭａｃｈｉｎｅが、デスクトップコンピューターよりも、２〜３桁速くなる（実際の数は、問題、およびこれらの最適化が開発され得る程度に依存する）。
【００９９】
アルゴリズムの全てがユーザーに対して透過性である。ユーザーは、ＧＵＩまたはコマンドラインを介してＢＬＡＳＴジョブを入力し、そしてソフトウェアは、自動的に、ユーザのさらなる介入なしで全ての適用可能な最適化を適用する。ＢｌａｓｔＭａｃｈｉｎｅは、数週ではなく、数時間でゲノムスケールの問題を解決する（例えば、ヒト転写データベースとヒトアンサンブルデーターベースとの比較は、ＮＣＢＩ ＢＬＡＳＴ２．１．２を実行するＡｌｐｈａシステムでの９日間と比較して、ＢｌａｓｔＭａｃｈｉｎｅでたった３時間かかった）。さらに、Ｐａｒａｃｅｌ ＢＬＡＳＴは、特定のジョブを自動的に管理可能な部分に分割し、そして従って、他のアーキテクチャー（例えば、全てのヒトＥＳＴを染色体に配置する）では失敗するような検索を完了するように実行する。さらに多くのゲノムスケールのデータセットが利用可能になるにつれて、本発明者らは、この種の最適化ツールが、大規模なデータ分析およびマイニングについてに有用性は増大する。
【０１００】
本発明は、本発明の精神または必須の特徴から逸脱することなく、他の特定の形態で具体化され得る。従って、上記実施形態は、本明細書中に記載される本発明を限定するというよりもむしろ、本発明の例示の全ての局面において考慮されべきである。従って、本発明の範囲は、上記記載によってよりもむしろ、添付の特許請求の範囲によって示され、そして従って、特許請求の範囲に等価な意味および範囲に入る全ての改変は、そのなかに含まれると意図される。さらに、本明細書中に記載される改善が、ＤＮＡおよびペプチドのような生物学的情報の配列に制限されず、任意の種の文字列検索に適用可能であることが企図される。
【図面の簡単な説明】
【０１０１】
【図１】図１は、ハイスコアセグメントペアを表す有向閉路グラフを提供する。
【図２】図２は、本発明の１つの実施形態に従う、ＢｌａｓｔＭａｃｈｉｎｅシステムアーキテクチャの高レベルのブロックダイアグラムを例示する。
【図３】図３は、クエリーチョッピングの図式的表現を例示し、ここで、オリジナルクエリーは、重なりのある（オーバーラップ）サブクエリーへと切断（チョップ）され、これは、次いで、本発明の実施形態に従って、分散され得る。
【図４】図４は、本発明の１つの実施形態に従って、様々なＨＳＰのタイプをクエリーチョッピングすることの図式表現を例示する。
【０００１】
（関連出願）
本出願は、「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｈｉｇｈ−Ｓｐｅｅｄ Ａｐｐｒｏｘｉｍａｔｅ Ｓｕｂ−Ｓｔｒｉｎｇ Ｓｅａｒｃｈｅｓ」と題する米国仮特許出願第６０／２８８，４６５号（２００１年５月４日出願）（この全体は、本明細書中にて参考として援用される）の優先権の利益を、米国特許法第１１９条（ｅ）項に基づき主張する。
【０００２】
（発明の分野）
本発明は、文字列検索に関連し、より具体的には、コンピュータに実装された、データベースの文字列検索に関する。
【背景技術】
【０００３】
（発明の背景）
核酸（例えば、ＤＮＡ）またはタンパク質の新規の並びが配列決定されると、その配列は、代表的には、既知の、ＤＮＡ情報およびタンパク質情報のデータベースに対して比較され、この新規ＤＮＡまたは新規タンパク質の機能の予備的な表示を提供する。次いで、研究者は、このデータベース検索の結果を評価するための実験を設計し得る。
【０００４】
ＤＮＡ配列決定技術の甚大な改善の結果として、ＤＮＡデータベースの増大する速度は、１９８９年の１年間当たり１５０万ヌクレオチドから１９９９年の１年間当たり１６億を超えるヌクレオチドへと、最近の１０年に亘って指数関数的に増大した。１９９９年以降、ショウジョウバエ、マウス、およびヒトのゲノムを含む全ゲノムが、配列決定されている。既知の遺伝的配列情報の量が指数関数的に増大するに従って、この増えつつある配列データベースを検索するための高速な方法の開発がますます重要なものとなった。
【０００５】
例えば、ゲノム情報の公的な集積機関である、ＧｅｎＢａｎｋは、現在、おおよそ、１６ＧＢのデータを所有している。これは、１９８２年において６８０Ｋにすぎなかったものから増大している（Ｂｅｎｓｏｎら，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２８（１：１５−１８（２０００）（ｗｗｗ．ｎｃｂｉ．ｎｌｍ．ｎｉｈ．ｇｏｖ／Ｇｅｎｂａｎｋ／ｇｅｎｂａｎｋｓｔａｔｓ．ｈｔｍｌもまた参照のこと））。この速度では、データ量は、１６．５ヶ月毎に２倍となる。２００１年だけでも、総計３ＧＢに及ぶ３５０万配列の新規配列が、ＧｅｎＢａｎｋに入力された。公開配列決定設備または専用配列決定設備の両方とも、２４時間体制でデータを生成するウェアハウス標準のファクトリーからなり、これは、試薬の利用および配列決定機器の速度にのみ制限される。
【０００６】
より多くの配列データが利用可能になると、最も根本的な問題の１つは、配列アライメント（すなわち、新たに発見された、ヌクレオチド配列またはアミノ酸配列が、それまでに既知でありかつ研究されているデータとどのような関係にあるかということ）である。いずれにしても、配列データ量が２倍になると、可能な比較の数は、４倍になるということに留意されたい。従って、おおよそ同じ時間経過で、コンピュータ速度が指数関数的に倍加する同様の印象があったとしても、配列比較アルゴリズムは、利用可能なデータの中いずれの有意な部分についての相同性を見出す能力において、ますます遅れをとっている。
【０００７】
相同性検索における現在の研究の多くは、より感度が高くかつより選択的であるアルゴリズムに集中しており、このアルゴリズムは、偽陽性および偽陰性の割合を低減するため、換言すると、微弱な相同性（例えば、遠縁の２つの生物の遺伝子）を正確に同定するため、例えば、以下に記載される、隠れマルコフモデルにような精巧な技術を使用するアルゴリズムである：Ｅｄｄｙ、「Ｐｒｏｆｉｌｅ Ｈｉｄｄｅｎ Ｍａｒｋｏｖ Ｍｏｄｅｌｓ」、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，１４（９）：７５５〜７６３（１９９８）（この全体は、本明細書中で参考として援用される）。このようなアルゴリズムは、利用可能なデータから最大量の情報を得ることのより高いレベルを求め、そして、おおいに研究的に興味深い。本発明は、異なった路線をとる。多くの用途について、既存のアルゴリズムは、十分良好である。特に、アルゴリズムにおけるＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ）ファミリ（ＮＣＢＩにより開発された）は、殆どの検索に対して十分に感度が高く、かつ選択的である。例えば、Ａｌｔｓｃｈｕｌら，「Ｇａｐｐｅｄ ＢＬＡＳＴ ａｎｄ ＰＳＩ−ＢＬＡＳＴ：ｎｅｗ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｏｔｅｉｎ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ｐｒｏｇｒａｍｓ」，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２５（１７）：３８９−３４０２（１９９７）（この全体は、本明細書中で参考として援用される））を参照のこと。
【０００８】
（ＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ））
現在、高速データベースの最も一般的な方法は、Ａｌｔｓｃｈｕｌら，Ｊ．Ｍｏｌ．Ｂｉｏｌ．，２１５（３）：４０３−１０（１９９０）（この全体が、本明細書中で参考として援用される）に記載されたＢＬＡＳＴ（Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ）の改良型である。ＢＬＡＳＴおよびその改良型は、高速な、配列のローカルアライメント（局所的アライメント）を提供する。ＢＬＡＳＴプログラムは、タンパク質またはＤＮＡのクエリー（問合せ配列）と、タンパク質またはＤＮＡのデータベースとを、任意の組み合わせで比較するように記述されており、ここで、ＤＮＡ配列は、これらの任意の比較が実行される前に、概念上の翻訳をしばしば受ける。
【０００９】
ＢＬＡＳＴは、類似性の指標を最適化することを試みるヒューリスティック（発見的）なものである。具体的に、ＢＬＡＳＴは、ランダムなアライメントとは統計学的に区別され得る類似性のある全ての局所領域（ハイスコアセグメントペア（Ｈｉｇｈ−ｓｃｏｒｉｎｇ Ｓｅｇｍｅｎｔ Ｐａｉｒ）（ＨＳＰ）と呼ばれる）を同定する。ＢＬＡＳＴは、「閾値」パラメータであるＴを設定することによって、速度と感度との間の折り合いを可能にする。より高い値のＴによって、より高速となるが、また、微弱な類似性を取りこぼす可能性も増大させる。このＢＬＡＳＴプログラムは、クエリーの長さと検索されるデータベースの積に比例して時間を必要とする。
【００１０】
ＢＬＡＳＴアルゴリズムの中心的な概念は、統計的に有意なアライメントは並置されたワードのＨＳＰを含む可能性が高いということである。ＢＬＡＳＴは、まずはじめに、このクエリー配列内のいくつかのワードと並置されたときに少なくともＴのスコアを持つワード（例えば、タンパク質に対して３、ＤＮＡについて１２のワード）についてデータベースをスキャンする。この条件を満たす並置された任意のワードペアは、「ヒット」と呼ばれる。このアルゴリズムの第２の工程によって、各ヒットが、アライメントの中に報告されるのに十分なスコアで存在するか否かを評価される。これは、実行中のアライメントのスコアがそれまでに得た最大値からＸよりも低下するまで、両方向へヒットを伸長させていくことにより実行される。
【００１１】
その殆どの基本的な実装において、このＢＬＡＳＴアルゴリズムは、以下の３つの工程を実行する：（１）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルし；（２）データベース中の配列の各々に対して、閾値Ｔよりも高いスコアを有するワードヒット（すなわち、データベースの配列の中のワードと一致するクエリー配列に由来するワード）をスキャンし；（３）ワードヒットの各々について、Ｓ以上のスコアのハイスコアペア（ＨＳＰ）を形成するように両方向にワードヒットを伸長していく。以下のパラグラフで、これらの工程を詳細に説明する。
【００１２】
代表的なＢＬＡＳＴの実装において、ハイスコアワードのリストがｉ行×ｊ列のルックアップテーブルの中に作成され、ここで、ｉは、長さｗの可能なワードの全ての数であり、そして、ｊは、（クエリー配列におけるエレメントの数）−ｗである。値ｉは、長さｗの全ての可能なワードを表すので、このルックアップテーブルにおける行の各々は、長さｗの１つのワードに対応する。この行番号は、その対応するワードの字句順序（ｌｅｘｉｃａｌ ｏｒｄｅｒ）に対応し、そして、これはそのワードに関する「行番号」とみなされ得る。ＤＮＡ配列に関して、ｉ＝４ｗであり；タンパク質配列に関して、ｉ＝２０ｗである。このｊ値は、クエリー配列の中の、長さｗであるワードの開始位置の番号を表す。このルックアップテーブルは、全て０として初期化され、次いで、以下のように配置（ｐｏｐｕｌａｔｅ）される：クエリー中の長さｗのワードそれぞれについて、その対応する行を参照する。この行ｘを呼びだす。クエリー配列ｙにおけるワードの位置を呼び出す。このルックアップテーブルの（ｘ，ｙ）要素をｙに設定する。一旦、このルックアップテーブルが配置されると、次いで、取り除かれる（ｔｒｉｍ）。全て０を有する行は、クエリーにおいて存在しないワードを表すので、取り除かれる。次いで、残りのワードは、それらのワードを調べてこれらのセルフ類似性スコアが最小閾値Ｔを満たすか否かを判断することによって、有意性についてスクリーニングされる。類似性スコアは、代表的には、以下に記載されるような置換マトリックス（例えば、ＰＡＭ１２０およびＢＬＯＳＵＭ６２）を使用して計算される：Ｄａｙｈｏｆｆら，Ａｔｌａｓ ｏｆ Ｐｒｏｔｅｉｎ Ｓｅｑｕｅｎｃｅ ａｎｄ Ｓｔｒｕｃｔｕｒｅ，Ｖｏｌ．５，Ｓｕｐｐｌ．３，Ｅｄ．Ｍ．Ｏ．Ｄａｙｈｏｆｆ（１９７８）；Ｈｅｎｉｋｏｆｆ ａｎｄ Ｈｅｎｉｋｏｆｆ，Ｐｒｏｃ．Ｎａｔｌ．Ａｃａｄ Ｓｃｉ．ＵＳＡ，８９：１０９１５−１０５１９（１９９２）；ならびにＨｅｎｉｋｏｆｆおよびＨｅｎｉｋｏｆｆ，Ｐｒｏｔｅｉｎｓ，１７：４９−６１（１９９３）。これらの刊行物は、本明細書中において、参考としてその全体が援用される。Ｔ未満のセルフスコアを有するワードを表す行は、削除される。最終的に、ゼロ（０）を有する全ての列が取り除かれる。得られたルックアップテーブルは、有意なワードの字句ワード数（ｌｅｘｉｃａｌ ｗｏｒｄ ｎｕｍｂｅｒ）によって、索引付けされ、そして、クエリー配列における有意なワードの位置を戻す。
【００１３】
ＢＬＡＳＴはヒューリスティックアルゴリズムであり、そして、ｗおよびＴの値は、感度、特異性、および速度の最適な組み合わせについて選択される。所定値Ｔについてｗが増加すると、特異性は向上するが、感度は低下する。同様に、所定値ｗについてＴが減少すると、感度は向上するが、特異性は低下し、実行時間は増大する。ｗおよびＴの例示的な設定は、タンパク質について、ｗ＝４、Ｔ＝１７であり、ＤＮＡについては、ｗ＝１２，Ｔ＝６０である。
【００１４】
一旦、このルックアップテーブルが構築されると、これは、クエリー配列をこのデータベースに対して比較するために使用される。具体的には、このデータベースは、そのセルフスコアは閾値Ｔよりも高いクエリー配列の中に存在する長さｗの全てのワードに対して検索される。従って、見出された全てのワードは、「ヒット」と称される。データベース検索の出力（アウトプット）は、ヒットのリストを含む。このデータベースが反復して検索されるので、このデータベースは、クエリー配列に対して生成されたルックアップテーブルに類似の、ルックアップテーブルへと前処理される。従って、この検索プロセスは、２つのルックアップテーブルを比較することによって、迅速に実施され得る。
【００１５】
この最終工程は、各ヒットを伸長させてハイスコアセグメントペア（ＨＳＰ）を形成することである。代表的には、このヒットは、クエリー配列およびデータベース配列の対応する並び（ストレッチ）の間の類似性スコアが予め決定した閾値Ｓ未満に低下するまで、両方向に伸長される。代表的なＢＬＡＳＴ実装の出力は、このデータベースにおいて見出されたヒットの記述を含む。ヒットの各々に対して、この出力は、ヒットが現れた配列についての情報、そのヒットのビットスコア、与えられたＨＳＰが偶然に見出される確率、およびＥ値（これは、この与えられたスコアに関して、このサイズのデータベースにおいて偶然に見出されたと期待される一致の数の指標である）を含む。
【００１６】
（ＢＬＡＳＴにおける以前の改良）
ＢＬＡＳＴアルゴリズムの実装は、このアルゴリズムが最初に導入されたとき以来、改良を受けている。３つの主要な改良として、ヒット伸長のための「ツー・ヒット（ｔｗｏ−ｈｉｔ）」法、ギャップ付きアライメントを生成する能力、および微弱であるが生物学的に関連性にある配列類似性に対して多くの場合においてより感度が高い「ＰＳＩ−ＢＬＡＳＴ（Ｐｏｓｉｔｉｏｎ−Ｓｐｅｃｉｆｉｃ ｉｔｅｒａｔｅｄ ＢＬＡＳＴ）」が挙げられる。これらの改良型は、例えば、Ａｌｔｓｃｈｕｌ，「Ｇａｐｐｅｄ ＢＬＡＳＴ ａｎｄ ＰＳＩ−ＢＬＡＳＴ：ａ ｎｅｗ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｐｒｏｔｅｉｎ ｄａｔａｂａｓｅ ｓｅａｒｃｈ ｐｒｏｇｒａｍｓ」，Ｎｕｃｌｅｉｃ Ａｃｉｄｓ Ｒｅｓｅａｒｃｈ，２５（１７）：３３８９〜３４０２（１９９７）に詳細に説明されている。
【００１７】
オリジナルのＢＬＡＳＴの実装の性能データは、その伸長工程（ここでは、ヒットが伸長されてＨＳＰを生成する）が処理時間の最大量を費やしたことを示している。ヒットの伸長のための「ツー・ヒット」法は、この工程における改良であり、この改良によって、費やす時間がずっと短い伸長工程が作り出される。実験的証拠によって、目的とする代表的なＨＳＰは、単独のワードペアよりもずっと長く、それに従って、同じ対角線（ｄｉａｇｏｎａｌ）上で互いに比較的短い距離内に複数のヒットを含み得ることが示されている。このツー・ヒット法は、伸長が始まる前に、同じ対角線上にあり、かつ互いに距離Ａの内にある、２つの重なっていないワードペアの存在を必要とすることによって、この観察結果を利用する。最も新しいヒット（ｔｈｅ ｍｏｓｔ ｒｅｃｅｎｔ ｏｎｅ）と重なっているヒットは全て、無視される。この方法は、伸長をすすめるために１つのヒットではなく、２つのヒットを必要とするので、この閾値パラメーターＴは、同等の感度を保持するほど低くなければならない。この効果は、多くの単独のヒットが見出されるが、少数の部分のみが、伸長を引き起こす同一の対角成分上において随伴する第２のヒットを有するということである。従って、ヒットのかなり多くの部分は、適切な対角成分について、最も近いヒットの座標（ｃｏｏｒｄｉｎａｔｅ）を調べ、その最も近いヒットが、そのときのヒットの座標から距離Ａ内にあるか否かを評価し、そして、最後に、新しい座標でこの座標を置換するという僅かな計算の後に、簡単に処理を終了し得る。経験的に、少ない伸長を必要とすることによって省かれる計算量によって、より多くのヒット数を処理するために必要とされる余分な計算量が相殺される。
【００１８】
この伸長工程を実施する別の方法が、例えば、以下に記載されている：「Ｍｕｌｔｉｐｌｅ ｓｅｑｕｅｎｃｅ ａｌｉｇｎｍｅｎｔ ｕｓｉｎｇ ｂｌｏｃｋ ｃｈａｉｎｉｎｇ」、Ｚｈｅｎｇ Ｚｈａｎｇ，博士論文，Ｔｈｅ Ｐｅｎｎｓｙｌｖａｎｉａ Ｓｔａｔｅ Ｕｎｉｖｅｒｓｉｔｙ，ＵＭＩ Ｄｉｓｓｅｒｔａｔｉｏｎ Ｓｅｒｖｉｃｅｓ，Ａｎｎ Ａｒｂｏｒ（１９９６）；およびＺｈａｎｇら、「Ｃｈａｉｎｉｎｇ ｍｕｌｔｉｐｌｅ−ａｌｉｇｎｍｅｎｔ ｂｌｏｃｋｓ」，Ｊ．ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ，１：２１７− ２２６（１９９４）。この方法は、有向閉路グラフに関する古典的な最適経路アルゴリズムの特別な場合である、「ブロック連鎖」として知られているコンピュータ科学の既知のクラスの問題に対する伸長工程の類似性に基づいている。上述の方法は、Ｋ−Ｄツリーと称されるより高い次元の計算幾何学の周知の技術を採用する。一般的に、Ｋ−Ｄツリーは、セルが、過剰の入力オブジェクト含まないように、相対的に小さい数のセルへと多次元空間を階層的に分解するために使用される（Ｂｅｎｔｌｅｙ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１８：５０９−５１７，（１９７５）（これの全体が、本明細書中で参考として援用される）を参照のこと）。Ｚｈａｎｇにおいて、Ｋ−Ｄツリーを使用して、可能なブロック鎖の空間を領域へと分解するのに使用され、従って、このブロック連鎖問題を、連鎖領域（ｃｈａｉｎｉｎｇ ｒｅｇｉｏｎ）の計算機的にはそれ程負荷がかからない問題へと単純な形にする。Ｋ−Ｄツリーの使用によって、複数の配列比較（すなわち、２つを超える配列が、互い比較される）にとって有意な計算的利得を提供する。
【００１９】
ギャップ付きアライメントを生成する能力によって、ＢＬＡＳＴ性能における有意な改良が可能となる。オリジナルＢＬＡＳＴプログラムは、一緒に考えた場合のみにおいて、統計学的に有意な単独のデータベース配列を含むいくつかのアライメントをしばしば見出す。これらのアライメントのうちの任意の１つを見落とすことによって、全てを含めた結果に支障をきたす。ギャップ付きアライメントを生成するためのアルゴリズムを導入することによって、有意な全てを含めた結果において、部分的にまとめられたギャップなしのアライメントよりもただ１つののみを見出すことが必然となる。これによって、パラメータＴが上昇することを可能にし、初期データベーススキャンの速度を向上させる。ギャップ付きアライメントを生成する１つの方法は、ヒューリスティックアプローチ（これは、ＨＳＰを構築するためのＢＬＡＳＴ法におけるありふれた生成法である）を使用する。このアプローチの中心的な概念は、５０データベース配列ごとに、おおよそ１を超えない伸長が生じるように選択した、中程度のスコアＳｇを超える任意のＨＳＰについてギャップ付きの伸長を引き起こすことである。統計学的な分析によって、Ｓｇが、代表的な長さのタンパク質クエリーに対して約２２ビットで設定されるべきであることが示されている。ギャップ付き伸長は、ギャップのない伸長よりも長く実行するための時間を必要とするが、極少数のギャップ付き伸長を実行することによって、ギャップ付き伸長が費やす、総実行時間に占めるその割合は比較的に低く押さえら得る。さらに、ギャップのないアライメントのコレクションというよりも、単一のギャップ付きアライメントを探索することによって、構成するＨＳＰのうちの１つのみが、首尾よく生成された総合した結果について位置付けられる必要がある。これは、任意の単一の中程度のスコアをもつＨＳＰを失う可能性がずっと高いことを、許容され得ることを意味する。これによって、このアルゴリズムのヒットステージについてのパラメータを実質的に上昇させることを可能にするが、他方、匹敵する感度を保持している。例えば、Ｔは、オリジナルＢＬＡＳＴ実装の１ヒットヒューリスティックに関して、１１〜１３に向上した。
【００２０】
位置特異的スコアマトリクス（プロファイルまたはモチーフとして知られている）に対してＢＬＡＳＴを反復適用することによって、微弱であるが、生物学的に有意な関係がかなり頻繁に検出されるデータベース検索が可能となる。ＰＳＩ−ＢＬＡＳＴと称される位置特異的であって、反復されるＢＬＡＳＴの１つの実装は、最初のＢＬＡＳＴ実行の出力から位置特異的スコアマトリックスを構築し、その後のＢＬＡＳＴ実行のためのクエリーとしてそのマトリックスを使用する。
【００２１】
いくつかの精緻化が、ＢＬＡＳＴの現行の実装の、その速度、感度、および特異性を、そのオリジナルと比較したときに３倍を超えるまで向上させてきたが、配列データベースの増大の指数関数的な速度は、このアルゴリズムの実装に対しての絶え間ない改善を必要としている。
【００２２】
（並列処理）
大規模データベース検索を高速化するための１つのアプローチは、並列処理を使用することである。高性能並列計算（ハイパフォーマンスパラレルコンピューティング）は、複数のプロセッサにまたがって、大規模で複雑なタスクを分割することによって達成される。１つの単純な例として、配列データベースは、いくつかの部分（パート）へと細分化され得、各部分は、特定の処理単位へと割り当てられ得る。次いで、同じクエリーが、同時に、全ての処理単位において実行され得、各処理単位は、そのデータベースの一部分のみを検索する必要がある。より複雑な例として、タスクがサブタスクに分割される。例えば、ＢＬＡＳＴにおける伸長工程は、ＨＳＰの選択的な鎖について膨大な吟味を必要としている。この例においては、可能な鎖の空間は、複数の部分空間に細分化され、そして、部分空間の各々は、別個のプロセッサに割り当てられる。
【００２３】
様々な方法を使用して、複数の計算機（コンピュータ）における効率の改善が達成され得るが、並列処理を組織化し、かつそれを調整する最も一般的な方法は、目前にある問題を自動的に分解し、そして、プロセッサが、これらの作業を実行している間に、必要とされる場合に相互通信することを可能にするコードを記述することである。上記の第１の例において、プロセッサが、データベースの部分において、クエリーに対するマッチ（一致）を見出すと、このプロセッサは、それらの検索を実行している他のプロセッサに、そのイベントを信号で送信し得る。上記に第２の例において、プロセッサが新たな最大スコアを見出した場合に、そのプロセッサは、そのイベントを信号で送信し得、その結果、他のプロセッサは、それらの閾値を上昇させる。
【００２４】
並列処理の殆どのアプリケーションは、通常、プロセッサ間である程度の相互作用を必要とし、したがって、それらのプロセッサは、情報を交換するために相互に通信し得なければならない。例えば、マップ上のセルに対する値は、それらの最近接セルの値に依存し得る。このマップが２つの部分に分解されるとき、各々は、別個のＣＰＵ上で処理され、このプロセッサは、セル値を、そのマップの隣接エッジにおけるセル値と交換しなければならない。同様に、配列アライメントがいくつかのローカルアライメントに分解される場合、各ローカルアライメントを取り扱うプロセッサの各々は、その元の境界を越えてアライメントを伸長させるために、隣接するアライメントを取り扱うプロセッサと通信し得なければならない。
【００２５】
並列処理に対するいくつかの対照的なアプローチが存在する。例えば、並列処理は、高度に専用化したハードウェアまたは商用既製（ｃｏｍｍｅｒｃｉａｌ ｏｆｆ−ｔｈｅ−ｓｈｅｌｆ；ＣＯＴＳ）ハードウェア上にて実施され得る。ＢＬＡＳＴおよび他の配列比較およびデータベース検索のアルゴリズムアルゴリズムは、高度に専用化した、並列処理ハードウェア（例えば、ＰＡＲＡＣＥＬ’Ｓ ＧＥＮＥ ＭＡＴＣＨＥＲマシン）において実装されている。Ｕｌｌｎｅｒの米国特許第６，１１２，２８８号（この全体が、本明細書中で参考として援用される）に記載されるように、ＰＡＲＡＣＥＬ製ＧＥＮＥ ＭＡＴＣＨＥＲは、プログラム可能な特別目的のパイプラインプロセシングシステムを使用し、このシステムは、複数のアクセラレータチップを直列接続して備える。このアクセラレータチップの各々は、インストラクションプロセッサを備える。このパイプラインプロセッサセグメントの各々は、複数のパイプラインプロセッサを直列接続して備える。このように専用ハードウェアは、有意な速度向上を提供し得、特に、ダイナミックプログラミング（ＤＰ）アルゴリズムに関して有意な速度向上を提供し得る。
【００２６】
この専用ハードウェアアプローチと対照的なのは、コモディティ並列処理アプローチであり、これは、安価な商用既製（「ＣＯＴＳ」）ハードウェアを使用する。コモディティ並列処理にとって一般に普及しているアプローチは、以下に説明されるようなＢｅｏｗｕｌｆクラスタである：Ｂｅｃｋｅｒら，Ｂｅｏｗｕｌｆ：Ａ Ｐａｒａｌｌｅｌ Ｗｏｒｋｓｔａｔｉｏｎ ｆｏｒ Ｓｃｉｅｎｔｉｆｉｃ Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｒｏｃｅｅｄｉｎｇｓ，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ Ｐｒｏｃｅｓｓｉｎｇ（１９９５）；およびＭ．Ｓ．Ｗａｒｒｅｎら，Ｐａｒａｌｌｅｌ ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ ｗｉｔｈ ｃｏｍｍｏｄｉｔｙ ｃｏｍｐｏｒａｅｎｔｓ；Ｈ．Ｒ．Ａｒａｂｎｉａ編，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ（ＰＤＰＴＡ’９７），１３７２−１３８１頁，１９９７（これらの刊行物は、本明細書中で、それらの全体が参考として援用される）。Ｂｅｏｗｕｌｆ型クラスタは、専用高速ネットワークによって相互接続されたコモディティハードウェアコンポーネント（ＬｉｎｕｘまたはＦｒｅｅＢＳＤのようなフリーソフトウェアである基本ソフト（ＯＳ）を動作させる）から主に構築される、高性能の、大規模並列計算機である。代表的なＢｅｏｗｕｌｆ型クラスタは、ハイパフォーマンスコンピューティングタスクの実行専用の、複数の相互接続した、ＰＣまたはワークステーションを備える。これは、通常、シングルノードのみを介して、外部と接続されている。代表的なＢｅｏｗｕｌｆ型クラスタは、メッセージパッシングと称されるプロセッサ間通信の一般に普及している方法を使用する。メッセージパッシングの一般に普及している実装は、「ＰＶＭ（Ｐａｒａｌｌｅｌ Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ）」および「ＭＰＩ（Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ Ｉｎｔｅｒｆａｃｅ）」を含む。
【発明の開示】
【発明が解決しようとする課題】
【００２７】
コモディティ並列処理ハードウェアは、妥当なコストでかなりの性能を提供し、かつ、指数関数的なデータベースの増大がデータベース検索における実質的な改良を必要としているために、コモディティ並列処理ハードウェア上のＢＬＡＳＴアルゴリズムの性能を向上させるようにＢＬＡＳＴアルゴリズムを改良する必要性が存在する。
【課題を解決するための手段】
【００２８】
（発明の要旨）
本発明は、単一のデスクトッププロセッサにより実行される従来型のＢｌａｓｔアルゴリズムよりも２桁から３桁の規模で、より高速である改良型ＢＬＡＳＴアルゴリズムを実装するための一体型（ｃｏｍｂｉｎｅｄ）ハードウェア−ソフトウェアシステムを使用する、方法およびシステムを提供することによって、上記の要求および他の要求に取り組む。本発明システムのソフトウェアコンポーネントは、本明細書中において、Ｐａｒａｃｅｌ ＢＬＡＳＴと称され、そしてそのハードウェアコンポーネントは、本明細書中において、Ｐａｒａｃｅｌ ＢｌａｓｔＭａｃｈｉｎｅとして称される。本明細書中で教示される技術に従って、このＢｌａｓｔＭａｃｈｉｎｅ上でのＰａｒａｃｅｌ ＢＬＡＳＴによって、ゲノム規模のデータセットの操作が可能であり得る。アルゴリズム的な改良および並列ハードウェアアーキテクチャによって、このＢｌａｓｔＭａｃｈｉｎｅが、他の技術を用いて解決可能な問題よりも、重大で大きな問題を解決することを可能とする。１つの実施形態において、このシステムは、ゲノムの第１のパス分析について十分適しており、これにより、その後の段階における、より精巧な遅いアルゴリズムおよび手動による介入を可能にして、この第１のパスが残していたギャップを満たすことを可能にする。
【００２９】
１つの局面において、本発明は、データベース検索を並列化するために、動的データベース分割を実行するための、構造体おひよび方法を提供する。
【００３０】
別の局面において、本発明は、単一のデータベース検索に対して複数のクエリーを併用するための、構造体および方法を提供する。
【００３１】
別の局面において、本発明は、クエリー配列とデータベース配列との間のより長いマッチを生成するためのハイスコアセグメントペアの十分な、連結および伸長のための構造体および方法を提供する。
【００３２】
１つの特定の実施形態において、本発明は、配列データベースに対して複数のクエリー配列を比較する為の方法に関し、この方法は、以下の工程を包含する：（ａ）複数のクエリー配列を、一体型クエリー配列に結合する工程；（ｂ）上記データベースの複数の下位区分を決定する工程；（ｃ）複数の検索を実施する工程であって、ここで、各検索は、上記データベースの複数の下位区分のうちの１つに対して一体型クエリー配列の比較を含む工程であって、これによって、複数のワードマッチを生成した工程；（ｄ）工程（ｃ）において生成された複数のワードマッチの長さを伸長する工程であって、複数のハイスコアセグメントペアを生成する工程；（ｅ）上記の複数のハイスコアセグメントペアを結合する工程；および（ｆ）複数のレーポートを作成する工程であって、各レポートは、複数のクエリー配列の１つに対する最もスコアの高いマッチ（一致）を示す工程。
【００３３】
複数の配列は、任意の方法による一体型クエリー配列へと結合され得る。例えば、本発明の方法の工程（ａ）において、複数に配列は、クエリールックアップテーブルに複数の配列を記憶すること、およびクエリー番号で上記配列の各々について索引作成し、それぞれのクエリー番号と上記の各配列を連結することによって、一体型クエリーに結合される。この結合プロセスは、任意の適切なパラメータ（例えば、長さパラメーター）を使用して、制御またはモニターされ得る。より具体的には、複数の配列は、上記テーブルに記憶されたデータ量が予め決定されていた制限値に達するまで、クエリールックアップテーブルにおいて記憶され得る。別の例において、本発明の方法の工程（ａ）において、複数の配列は、同時に複数のクエリーのハッシュを構築することによって、結合され得る。
【００３４】
このデータベースは、任意の適切な方法によって、複数の下位区分に分割され得る。例えば、このデータベースの複数の下位区分を決定する工程は、塩基数、および上記のデータベース中の配列の数で、上記のデータベースのサイズを特定して、このデータベースを検索することによって生成される結果に関する統計的に有意な値を計算する工程を包含する。他の例において、このデータベースは、ＢＬＡＳＴアルゴリズムに対して１以上の、以下の改変を行うことによって複数の下位区分に分割され得る：（ｉ）基礎的なＢＬＡＳＴアルゴリズムの少なくとも１つの統計学的パラメーターは、正しい部分的な結果を生成するように調整され；（ｉｉ）データベースにアクセスするための基礎的なＢＬＡＳＴアルゴリズムにおいて使用される入力／出力ルーチンのうちの少なくとも１つが、データベースのサブセットにアクセスすることを支援するように改変され；（ｉｉｉ）中間結果の複数のメモリイメージ（ｍｅｍｏｒｙ ｉｍａｇｅ）が生成され；そして／または（ｉｖ）このメモリイメージが再結合されて、単一の結合されたＢＬＡＳＴレポートを作成する。特定の実施形態において、この基礎的なＢＬＡＳＴアルゴリズムは、データベースのサイズおよびこのデータベース中の配列数の両方を特定して、このデータベースを検索することによって生成された結果の統計学的な有意性を計算するように調整される。別の特定の実施例において、コマンドラインで引数（−ｚ）を使用して、このデータベース全体の塩基のサイズを特定し、そして、コマンドラインオプション（−ｓ）を使用して、このデータベースにおける配列全体の数を特定する。パラメータ−ｚおよび−ｓに関する値は、これらの値が別段提供されない場合は、サブセット化されたデータベースのサイズ全体に基づいて自動的に計算される。このデータベースはまた、このデータベースの対象（ｓｕｂｊｅｃｔ）の開始を示す第１の序数（ｏｒｄｉｎａｌ）ＩＤ（Ｘ）を特定することによって、そして、このデータベースの対象の終端を示す第２の序数ＩＤ（ｙ）を特定することによって、複数の下位区分に分割され得、ここで、上記第１の序数ＩＤは、０〜Ｎ−１の範囲に及び、ここで、Ｎは、データベース中の配列数である。このデータベースは、任意の適切なサイズの部分に細分され得る。例えば、このデータベースは、ノードにおけるＲＡＭに適合するように十分小さい部分に細分され得る。
【００３５】
複数のワードマッチ（ｗｏｒｄ ｍａｔｃｈｅ）の長さは、任意の方法を使用して、本発明の方法の工程（ｄ）において伸長され得る。例えば、この伸長工程は、以下の工程を包含し得る：（ｉ）１セットのハイスコアセグメントペアを評価して、第１の基準に従う上記セットにおいて最もスコアの高い鎖を決定する工程であって、ここで、この鎖は、ハイスコアセグメントペアにおける上記セットのサブセットを含む工程；（ｉｉ）ハイスコアセグメントペアの上記セットから上記の鎖を取り出す工程；および（ｉｉｉ）このハイスコアセグメントペアが無くなるまで、上記の工程（ｉ）および（ｉｉ）を反復する工程。好ましくは、この評価工程（ｉ）は、第２の基準に従って再計算を必要としないハイスコアセグメントペアの上記セットにおけるサブセットを決定する工程を包含する。別の例において、複数のワードマッチの長さは、ｌｉｎｋ＿ｈｓｐｓ（）を用いて伸長される。この複数のワードマッチの長さは、別個のプロセッサ上で伸長され得る。あるいは、この複数のワードマッチの長さは、データベース検索を実行するために使用される、同一のプロセッサ上で伸長され得る。
【００３６】
この複数のハイスコアセグメントペアは、任意の適切な方法を使用し、本発明の方法の工程（ｄ）にて結合され得る。例えば、複数のハイスコアセグメントペアは、「ｐｂｍｅｒｇｅ」プログラムを使用して結合され得る。
【００３７】
本発明の方法は、適切な配列ハードウェア上で実行され得る。例えば、本方法は、商用既製（「ＣＯＴＳ」）ハードウェア上で実行され得る。好ましくは、本方法は、Ｂｅｏｗｕｌｆ型並列処理アーキテクチャで実行され得る。
【００３８】
本方法は、任意の適切なデータベースにおいて、任意のクエリー配列について検索を実行するために使用され得るが、但し、このクエリー配列は、このデータベースに含まれる少なくともいくつかの配列と適合性である。しかし、いくつかの環境においては好ましいのであるが、このクエリー配列がこのデータベースに含まれる全ての配列と適合性である必要はない。例えば、あるタンパク質配列は、核酸配列とに加えて、タンパク質の配列を含むデータベースにおける検索を実行するのためのクエリー配列として使用され得る。同様に、核酸配列（例えば、ＤＮＡ配列またはＲＮＡ配列）は、タンパク質配列に加えて、核酸配列を含むデータベースにおける検索を実行するためのクエリー配列として使用され得る。
【００３９】
本発明の方法は、ゲノム配列、ｃＤＮＡ配列、ＥＳＴ配列またはそれらの組み合わせを含むデータベースのような任意の適切な配列データベースにおける検索を実行するために使用され得る。本発明の方法は、公開データベース（例えば、ＧｅｎＢａｎｋ）または加入者限定データベースにおける検索を実施するのに使用され得る。
【００４０】
別の特定の実施形態において、本発明は、以下の工程を使用するＢＬＡＳＴアルゴリズムを用いるデータベースにおける配列検索を実行するための方法に関する：（ａ）クエリー配列から長さｗのハイスコアワードのリストをコンパイルして；（ｂ）このデータベースにおける各配列のついて、閾値Ｔを超えるスコアを有するワードヒットについてスキャンし；そして（ｃ）各ワードヒットについて、このヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアセグメントペア（ＨＳＰ）を形成し、ここで、改良型は、以下の（ｉ）、（ｉｉ）、（ｉｉｉ）のうちの１つ以上を含む：（ｉ）上記検索を実行する前に、複数のクエリー配列を一体型クエリー配列に結合する工程；（ｉｉ）上記検索を実行する前に、データベースの複数の下位区分を決定する工程；（ｉｉｉ）可能な何時においても、ハッシュテーブルは、プロセッサとメモリとの間で往来するのではなく、プロセッサキャッシュに留まるようにコードを再構築する工程；および／または（ｉｖ）１メガ塩基（１００万塩基または１００万塩基対）以上のクエリー配列を、上記の検索を実行する前に、より小さい部分に分割する工程（例えば、上記クエリー配列を、重複する部分に分割し、その検索において別々に、各部分を実行することによる）。好ましくは、このクエリー配列は、以下の工程によってより小さい部分に分割される：ａ）上記クエリー配列を複数の重なり合う（オーバーラップ）配列へと分割する工程；ｂ）重なり合う部分の各々が、唯一の重なり合う配列においてのみ含まれるように、上記における複数の重なり合う配列から、重なり合う部分を取り除く工程；およびｃ）除去を受けた部分が、上記の重なり合う部分の全体に及ぶ任意のＨＳＰを含むか否かを検出する工程であって、そして、このようなＨＳＰが検出された場合に、上記ＨＳＰを生じるオリジナルヒットを見出し、そして分割されていないクエリー配列の状況におけるＨＳＰを伸長する工程。このクエリー配列は、任意の適切なサイズ（例えば、約１０キロ塩基（１０００塩基または１０００塩基対））のより小さい部分へと分割され得る。
【００４１】
さらに別の具体的な実施形態において、本発明は、データベースにおける配列検索を実行する為のシステムに関し、このシステムは、マネージャーノードおよび複数のワーカーノードを備え、ここで、上記マネージャーノードは、クライアントステーションおよび上記ワーカーノードの各々に作動可能に接続されて、そして、上記システムは、上記の方法のいずれか１つに従って、データベース中の配列検索を実行することが可能である。１つの例において、ハードウェアのレベルで、このマネージャーモジュールは、デュアルＣＰＵマザーボード、ＲＡＭ、ディスク、およびネットワークカードを備えるマネージャーノードを備える。他のノード（例えば、ワーカーノード）は、類似のハードウェア（通常は、ディスクは備えない）を備える。１つの好ましい例において、このマネージャノードは、マネージャー「デーモン」（恒久的プロセス（ｐｅｒｓｉｓｔｅｎｔ ｐｒｏｃｅｓｓ））ソフトウェアをこのマネージャーノード上で実行させるが、ワーカーデーモンは、ワーカーノード上で実行させる。このマネージャーデーモンは、クライアントプロセスからジョブリクエストを受信する工程を担い、このクライアントプロセスは代表的にはクライアントワークステーションにおいて実行され、そのジョブリクエストを待ち行列にいれ（ｑｕｅｕｉｎｇ）、そのジョブリクエストをサブジョブまたはタスクに分割し、これらのタスクのスケジュール管理を行い、そして、それらのタスクをワーカーデーモンへと割り当てることを担っている。このワーカーデーモンは、マネージャーデーモンからのサブジョブをリクエストし、そして、そのマネージャーデーモに結果を戻す。
【００４２】
これらの要素（エレメント）およびアルゴリズムの操作の詳細な説明は、以下に提供される。本明細書中で引用される全ての参考文献は、その全体が参考として援用される。
【００４３】
（発明の詳細な説明）
開示の明確化のためであって、かつ、限定のためではなく、本発明の詳細な説明は、以下に続く小節に分割される。
【００４４】
（定義）
別段定義されない限り、本明細書中で使用される、全ての専門用語および科学用語は、本明細書中において、本発明が属する分野の当業者によって通常理解されるものと同じ意味を有する。本明細書中で参照される、全ての、特許、特許出願、公開された特許出願、および他の刊行物は、それらの全体が参考として援用される。
【００４５】
本明細書中で使用される場合、「ａ」または「ａｎ」は、「少なくとも１つ」または、「１つ以上」を意味する。
【００４６】
本発明の目的について、別段示されない限り、「ＢＬＡＳＴ」とは、Ａｌｔｓｃｈｕｌら，Ｊ．Ｍｏｌ．Ｂｉｏｌ．，２１５： ４０３−４１０（１９９０）（これらの全体が、本明細書中で参考として援用される）に記載の「Ｂａｓｉｃ Ｌｏｃａｌ Ａｌｉｇｎｍｅｎｔ Ｓｅａｒｃｈ Ｔｏｏｌ」アルゴリズムに基づくアルゴリズムをいう。「ＮＣＢＩ ＢＬＡＳＴ」とは、ＢＬＡＳＴアルゴリズムのＮＣＢＩ（Ｎａｔｉｏｎａｌ Ｃｅｎｔｅｒ ｆｏｒ Ｂｉｏｔｅｃｈｎｏｌｏｇｙ Ｉｎｆｏｒｍａｔｉｏｎ）版の実装のバージョン２．１．２をいい、これは、当該分野で周知である。
【００４７】
本明細書中で使用される場合、「ノード」とは、計算ツリー（ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｒｅｅ）または計算システムにおける別個のスポット（点）または位置をいう。ノードは、ＣＰＵ、プロセッサもしくはマイクロプロセッサまたはそれらの機能部分、あるいはそれらの組み合わせであり得る。例えば、コンピューティングクラスタ（計算クラスタ）の状況において、ノードは、単一のコンピュータであり得、これは、１以上のプロセッサ（ＣＰＵ）および個々に共用された他のハードウェア（例えば、メモリ（ＲＡＭ）またはネットワークカードなど）からなる。
【００４８】
本明細書中で使用される場合、「ｌｉｎｋ＿ｈｓｐｓ」は、ＮＣＢＩ ｂｌａｓｔツールのサブルーチンをいう。各クエリー配列および各データベース配列について、このルーチンは、これらの２つの配列の間の、初期段階において計算されたＨＰＳを連結し、これらの２つの配列がどの程度類似しているかを評価する。ｌｉｎｋ＿ｈｓｐｓの結果に基づいて、このプログラムは、ギャップ付きアライメントがこれらの配列ペアについて計算されるか否かを決定する。
【００４９】
（クエリーパッキング）
ＢＬＡＳＴにおいて、配列データベースにおける各クエリーの検索は、その検索を設定するために、計算上のオーバーヘッドを要求する。具体的には、ルックアップテーブルが、このクエリーに対して構築されることが必要とされる。いくつかのクエリーを１つの検索に対して連結することによって、１クエリー当たりの計算上のオーバーヘッドの量が低減され、そして、クエリー処理における全体の処理量は増大される。１つの実施形態において、このＢＬＡＳＴアルゴリズムは、複数のクエリー配列を、このデータベースの単一のスキャニングパスへと圧縮（パッキング）し、従って、複数の小さいなクエリーに対する処理時間を低減するが、一方で、同一の入力用クエリーについてＮＣＢＩ ＢＬＡＳＴで生成された結果と同一の結果を生成するように改変される。具体的には、このクエリールックアップテーブルは、「クエリー番号」と称される必要な索引と共に、いくつかのクエリーに由来する情報を含むように改変され、それぞれのクエリーとその情報を連結する。
【００５０】
一体化型クエリーの結果が、それを構成するクエリーの個々の検索によって生成された結果と同一であることは重要である。同一の結果が生成されることを確認するために、各クエリーに対して序数を割り当てかつその序数をハッシュテーブルの記入項目に追加することによって、ハッシュテーブル生成が複数のクエリーに対するスキャニングと組み合わされる。さらに、全てのスキャン後の段階を実行するために、別個の検索構造体が、各クエリーに対して維持されており、そのスキャン後の段階としては、対角成分計算（例えば、ギャップのない伸長、ギャップ付伸長、およびアライメント）が挙げられる。
【００５１】
この実施形態において、長さパラメータは、どれほど多くのクエリーデータが結合され得るかを決定するために使用され得る。ＢＬＡＳＴの従来技術の実装においては、、メインループが、クエリーをインプットとして受信し、そして、イタレーション（反復）毎に１つのクエリーを処理していた。本実施形態において、このメインループは、一体型クエリーの全長が、長さパラメータに到達するか、またはそれを上回るまで、クエリーを結合する内部ループを有し、そしてデータベース検索をこの一体型クエリーを用いて実行するように改変されている。この一体型データベース検索の結果は、一体型クエリーの全てにおいて有意なワードマッチの全てを含む。次の工程は、ＨＳＰへとこれらのワードを伸長することを包含する。この工程の対角成分プロセシング（ｄｉａｇｏｎａｌ ｐｒｏｃｅｓｓｉｎｇ）は、クエリー特異的であり、そして、全ての対角成分計算は、この内部ループ内でクエリー毎に独立して実行される。
【００５２】
１つの好ましい実施形態において、クエリー配列Ｑの各々およびデータベース配列Ｄの各々にとって、本発明の方法は、以下の処理工程を実行する。
１．閾値を幾分上回る、ＱおよびＤの全てのローカルアライメントである、Ａ１（Ｑ，Ｄ），Ａ２（Ｑ，Ｄ）．．．，Ａｎ（Ｑ，Ｄ）を見つけ出す。
２．上位ｎのスコアの高いデータベース配列Ｄについて、全てのアライメントである、Ａ１（Ｑ，Ｄ），Ａ２（Ｑ，Ｄ）．．．，Ａｎ（Ｑ，Ｄ）を報告する。
【００５３】
このＢＬＡＳＴに特定のものは、その内部工程であり、つまりアライメントを見出す工程である。ＢＬＡＳＴヒューリスティックにとって重要であるのは、統計学的に有意なアライメントが、並置されたワードにおけるハイスコアペア（ＨＳＰ）を含むという可能性があるというこである。このアルゴリズムはまずはじめに、クエリー配列とデータ配列との間の短く正確なマッチ（デフォルトの長さは、ヌクレオチドに対しては、１１であり、タンパク質に対しては、３である）について検索する。このような一致は、ヒットと称される。次いで、これらのヒットは、はじめは、ギャップなしで伸長され、次いで、ギャップ付きで伸長され、そして、所定の閾値を越えるこれらのＨＳＰが戻される。完全な伸長工程は、計算的には非常に負荷のかかるものであり、そして、ＢＬＡＳＴは、統計的にＨＳＰである可能性が高いそれらのペアについて完全なアライメントを計算することのみにより、不必要な計算を実行することを回避する。
【００５４】
Ｐａｒａｃｅｌ ＢＬＡＳＴにおいて最適化されたこのアルゴリズムのうちの１つの部分は、は、ヒット生成が生じる方法である。ヒット生成のためのアルゴリズムは、以下である：
１．クエリーをプリプロセスし、以下のハッシュテーブルを生成する：
（ｎマー，ｎマーが存在するクエリーの位置）
２．このデータベース配列を検討し、そして、ｎマーの各々について、ハッシュテーブルにおけるそのｎマーを調べる。このテーブルのインディックスにおける任意の位置が、ヒットである。
【００５５】
例えば、このクエリーがＭＳＬＰＴであると仮定する。従って、この３マーが、１）ＭＳＬ、２）ＳＬＰ、および３）ＬＰＴである。このハッシュテーブルは、表１に示される。従って、ＳＬＰを含むデータベース配列は、例えば、クエリーの第２位におけるヒットを生成する。
【００５６】
【表１】
アミノ酸の３マー（ＡＡＡ．．．ＹＹＹ）の各々について、このテーブルは、３マーが存在するクエリー内のそれらの位置についてのエントリーを含む。例えば、ＭＳＬは、第１位で現れる。
【００５７】
ＢＬＡＳＴアルゴリズムのうちで最も「費用のかかる」（メモリを消費する）データ構造の１つは、上述のハッシュテーブルである。非常に高いレベルで、このアルゴリズムは、以下のようである：
１．ハッシュテーブルを配置（ｐｏｐｕｌａｔｅ）する。
２．このハッシュテーブルにおけるヒットの各々に対して、さらなるプロセシングを実行する。
【００５８】
ＮＣＢＩ ＢＬＡＳＴコードは、このハッシュテーブルの任意の特別な管理をなんら行わない。Ｐａｒａｃｅｌ ＢＬＡＳＴは、このコードを再構築し、その結果、可能である何時においても、ハッシュテーブルが、プロセッサとメモリとの間を往来するのではなく、プロセッサのキャッシュにとどまる。このことは、このテーブル中の値をコードすることに幾分関連し、メモリの使用頻度および、従ってテーブルサイズを減少して、その結果、このテーブルは、そのキャッシュに対して最適化する。キャッシュアクセスは、メモリアクセスようりも有意に高速であるので、これは、実質的な速度の向上を生じる。
【００５９】
（動的データベース分割）
先行技術において、検索されるべき大規模データベースは、静的に、いくつかのより小さいデータベースに分割され得た。しかし、このような設定は、ＢＬＡＳＴ検索全体が、これらのより小さいデータベースの各々に関して実施されることを要求し、これらの従属的な検索における結果を結合する静的で効果的な方法は、存在しない。本発明の１つの実施形態において、このＢＬＡＳＴアルゴリズムは、単一の大規模データベースに対する検索を分割して、複数のより小さいデータベースがサブセットを表すように構築することによって、その単一のデータベースのサブセットに対する複数の検索へと分割することを支援するように改変される。この実施形態において、この結果は、自動的に再結合され、分割することなしにこのデータベース全体を検索することによって生成されたレポートと生物学的に等価である単一のＢＬＡＳＴレポートへを作成する。この改変された方法は、本明細書中で「動的データベース分割」と呼ばれ、以下の４つの領域において、その基礎的なＢＬＡＳＴアルゴリズムに対する改変を必要とする：第１に、この静的パラメータは、正確な部分的結果を生成するように調整される必要がある。第２に、このデータベースにアクセスするのに使用される入力／出力ルーチンは、このデータベースのサブセットへのアクセスをサポートするように改変される必要がある。第３に、中間結果のメモリイメージが、生成される必要がある。第４に、これらのメモリイメージが、適切に再結合され、単一のひとつになったＢＬＡＳＴレポート生成する必要がある。
【００６０】
ＢＬＡＳＴは、データベースのサイズおよびこのデータベースにおける配列数を使用して、このデータベースの検索によって生成された結果の統計学的な有意性を計算する。一貫した結果に到達するために、検索される、塩基におけるサイズおよびデータベース全体の配列数は、特定されなければならない。ＢＬＡＳＴの従来の実装は、コマンドライン引数（−ｚ）を提供して、静的な計算において使用されるデータベース全体の塩基のサイズを特定していたが、配列全体の数を特定するための対応する方法を提供していなかった。本発明の１つの実施形態において、新規のコマンドラインオプション（−ｓ）が、この番号を特定するために追加され、このオプションは、検索の間で、このコードによって参照される、このオプションのデータ構造に追加された。この実施形態において、静的パラメータを計算するコードは、このデータベース全体において含まれる実際の配列数によりはむしろ、この−ｓオプションの値を使用する。さらなる実施形態において、これらの−ｚおよび−ｓのパラメータの値は、別段提供されない限り、サブセット化されたデータベースのサイズ全体にもとづて自動的に計算される。
【００６１】
１つの実施形態おいて、このＢＬＡＳＴアルゴリズムは、データベースのサブセットを検索するように改変された。さらなる実施形態において、このデータベースのサブセットは、以下の命名法を使用して特定され得る：「ｄａｔａｂａｓｅ＃ｘ−ｙ」、ここで「ｄａｔａｂａｓｅ」は、データベース名であり、ｘは、検索において含まれる第１の序数ＩＤ（「ＯＩＤ」）であり、そして、ｙは、この検索において含まれる最後のＯＩＤである。この実施形態において、ＯＩＤは、０からＮ−１の範囲に及び、ここで、Ｎは、このデータベースにおける配列数である。なおさらなる実施形態において、このデータベースのサブセットは、以下の命名法を使用して、特定され得る：「ｄａｔａｂａｓｅ＃ｘ−ｙ＃ｎ」、ここで、ｎは、この特定されたサブセットにおける塩基数である。ｎが特定されないと、データベース全体のサイズが使用され、つまり、この数は、そのレポートにおけるサイズ情報にのみ影響する。
【００６２】
この実施形態において、ｒｅａｄｄｂサブルーチンにおけるメモリマップファイルの概念に基づき、ＮＣＢＩ ＢＬＡＳＴコードは、塩基変化を反映するように改変され得、このサブルーチンは、ｉｎｄｅｘｆｐファイル、ｈｅａｄｅｒｆｐファイル、およびｓｅｑｕｅｎｃｅｆｐファイルを、基礎的なｒｅａｄｄｂデータ構造体ＲｅａｄＤＢＦＩＬＥの中に含む。ＢＬＡＳＴの従来技術型の実装は、ｍｍａｐ（２）ＵＮＩＸ（登録商標）システムコールまたはその等価物を使用して（Ｎｌｍ＿ＭｅｍＭａｐＩｎｉｔを呼び出すことにより）ファイル全体がマップされることを可能にするのみであった。この実施形態において、ここでは、３つまでのファイルの範囲が、これらのインディクスファイル（索引ファイル）における、ヘッダー、配列、および多義性（ａｍｂｉｇｕｉｔｙ）のセクションについて、マップされることを可能にする。この実施形態において、インディックスファイルが、ｒｅａｄｄｂ＿ｎｅｗ＿ｉｎｔｅｎａｌにおいて読まれると、はじめは、これは、メモリマップを全く使用することなしに、最初にオープンされる。一旦、このファイル中の配列数が決定されると、このインディクスファイルは、クローズされ、そして、特定されたメモリマップについての、２つ（タンパク質）または３つ（ＤＮＡ）の範囲を用いてリオープンされる。ＯＩＤの範囲が使用されると、このヘッダーファイルおよび配列ファイルは、ｒｅａｄｄｂ＿ｎｅｗ＿ｉｎｔｅｎａｌによるＲｅａｄＤＢＦＩＬＥ構造体において計算され、そして記憶される。その後、それらは、それらがＲｅａｄＤＢＯｐｅｎＭＨｄｒＡｎｄＳｅｑＦｉｌｅｓでオープンされたときに、このファイルの範囲のみをマップするのに使用される。
【００６３】
１つの実施形態において、このＢＬＡＳＴアルゴリズムは、最終的なＢＬＡＳＴレポートのかわりに、出力として中間結果を生成するように改変される。この中間結果は、アライメントを生成する前の、ｂｌａｓｔａｌｌメインループにおける点において、動的データ構造体のメモリイメージの、順番に並べられたコピーである。この実施形態において、この点における動的データ構造体は、移動され、そして、各メモリブロックは、相対インディクスに対する絶対ＲＡＭアドレスから、記述されたメモリブロックへと変換される埋め込まれたポインタ（ｅｍｂｅｄｄｅｄ ｐｏｉｎｔｅｒ）情報にそって記憶される。この実施形態において、テキスト出力はこの段階においては生成されない。
【００６４】
この実施形態において、「ｐｂｍｅｒｇｅ」と呼ばれるプログラムが、上述のように、膨大なデータベースの複数の部分から中間的結果を読みとるために、そして、このメモリブロックのために動的メモリを割り当て、そして、埋め込まれたメモリレファレンスから、絶対ＲＡＭアドレスに対する相対インディクスに変換しも戻すことよって、それらを各々の等価なメモリイメージへと記述するために、書かれた。次いで、ｐｂｍｅｒｇｅプログラムは、複数の中間結果を、結果の単一のセットへと結合して、この結合した結果をスコアによってソートし、もっとスコアの低いアライメントを破棄し、リクエストされた数の最良のマッチを生じる。最終的に、ｐｂｍｅｒｇｅは、単一の結合されたＢＬＡＳＴレポートを出力として生成するために、上記のように、短く巡回する、ｂｌａｓｔａｌｌメインループの後端部分を実行する。
【００６５】
（ハイスコアセグメントペアを連結する工程）
発明の背景で説明したように、実験的証拠によって、ＢＬＡＳＴにおける計算時間の大半は、ヒットを伸長することによって、そして、特に、ギャップ付きの伸長を実施する場合に費やされることが実証されている。代表的な実装において、この工程は、ｌｉｎｋ＿ｈｓｐｓ（）と命名された関数によって行われる。発明の背景において説明した改良型をもってしても、ＢＬＡＳＴの計算時間の有意な量が、なおも、ｌｉｎｋ＿ｈｓｐｓ（）において費やされている。この関数およびｌｉｎｋ＿ｈｓｐｓ（）のコンテキストは、以下に説明される：クエリー配列およびデータベースが与えられると、このデータベース中の配列Ｓの各々について、ＨＳＰのセットＨをこの配列Ｓについて決定する。次いで、ｌｎｋ＿ｈｓｐｓ（）関数は、この配列ＳについてのＨＳＰのセットＨの統計学的有意性を推定し、統計学的有意性が予め決定された閾値を超えるとき、最も有意性のあるマッチのリストに配列Ｓを加える。一旦、これらの配列の全てが処理されると、ＢＬＡＳＴは、最も有意性のあるマッチにおいてギャップ付き伸長を実施し、そして、そのアライメントを出力する。
【００６６】
より詳細には、ｌｉｎｋ＿ｈｓｐｓ（）は、以下のアルゴリズムを実装する：（１）ＨＳＰのセットＨから最もスコアの高い鎖Ｃを探し出し；（２）このＣについての有意性を計算し；（３）ＨからＣを取り除き；そして（４）Ｈが無くなるまで反復する。鎖Ｃについてのスコアは、以下のように計算される：ｋ個のＨＳＰの順列Ｈ１，Ｈ２，．．．，Ｈｋからなり、ここで、Ｈｉは、Ｈｉ＋１よりも前であり、従って：
【００６７】
【数１】
【００６８】
【数２】
【００６９】
現在、ＢＬＡＳＴの代表的な実装は、大規模ギャップ生成（ｌａｒｇｅ ｇａｐ ｃｒｉｔｅｒｉｏｎ）および小規模ギャップ生成（ｓｍａｌｌ ｇａｐ ｃｒｉｔｅｒｉｏｎ）として知られている、２つの結合関数を使用する。大規模ギャップ生成によって、おおきなギャップが形成され得、そして、この結合ペナルティをゼロ（０）に設定する。小規模ギャプ生成によって、予め決定されている定数Ａを超えるギャップは許容されない。小規模ギャップ生成は、Ａ以下のギャップについて、そのペナルティを０に設定し、Ａを超えるギャップについて負の無限大であるとする。現行の実装は、Ｓ（ｈ）の各々を計算するのに時間Ｏ（ｋ）を必要とし、そして、Ｈで終る最高スコア鎖を見出すために時間Ｏ（ｋ２）を必要とする。全ての鎖を見出すには、時間Ｏ（ｋ３）がかかる。ｋがクエリー長に対して線形的に増大し、そして、ＢＬＡＳＴアルゴリズムの残りのものは、固定されたデータベースについて、クエリー長対して線形的に増大するので、ｌｉｎｋ＿ｈｓｐｓ（）は長いクエリー配列においては実行時間のボトルネックになる。この適用において他で議論されるように、本発明の１つの実施形態は、「クエリーパッキング」を使用し、この「クエリーパッキング」はいくつかのクエリーを鎖状に繋いだものを含み、従って、クエリー長を増大させる。実験的証拠は、１Ｍｂクエリーについて、計算時間の８０％までが、ｌｉｎｋ＿ｈｓｐｓ（）関数を実行することに費やされ得ることを実証している。ＨＳＰのセットＨにおいて、同一の開始要素（エレメント）を有するエレメントは、同じクラスの属している称される。上述のように、ｌｉｎｋ＿ｈｓｐｓ（）の１つの工程は、最も高いスコアの鎖Ｃを、ＨＳＰのセットＨから取り出すことである。鎖のスコアを計算することは、この鎖における先行する点に依存する様式で、実行されるので、上述したように、ＨからＣを取り出すことは、Ｈが存続している全てのＣ依存的なエレメントが再計算されることを要求している。定義によると、鎖における全てのＨＳＰは、同じクラスに属している。鎖が取り除かれると、このクラスの全ての残りのエレメントは、再計算されることが必要とされる。２つの別個のギャップ基準を使用するＢＬＡＳＴの１つの実装において、Ｈにおける各エレメントは、別個の２つのクラスに属してており；１つの基準に対して最良の鎖は、別の基準における異なるクラスからのエレメントを含み得る。現行の実装において、１つの基準における最良の鎖を取り出すことは、全てのクラスの他の基準が再計算されることを必要とする。本発明の１つの実施形態において、ｌｉｎｋ＿ｈｓｐｓ（）の性能は、この種類の再計算を避けることよって改善される。
【００７０】
ＨＳＰのセットＨ、２つのギャップ基準、およびＨにおけるエレメント（要素）ｈが与えらると、ｌｉｎｋ１（ｈ）は、基準１に従った最も高いスコアの鎖におけるｈに対するその前のＨＳＰであり、そして、ｌｉｎｋ２（ｈ）は、基準２に従った最も高いスコアの鎖におけるｈに対するその前のＨＳＰであることを意味する。フォレスト（ｆｏｒｅｓｔ）Ｆ１は、それらの親（ペアレント）にように、ｌｉｎｋ１（ｈ）を有するサブツリーのセットとして定義される。同様にして、フォレストＦ２は、それらの親（ペアレント）として、ｌｉｎｋ２（ｈ）を有するサブツリーのセットとして定義される。一般に、Ｆ１におけるエレメント（要素）ｈが取り除かれると、ｈにおいてルートを有する部分ツリー（サブツリー）におけるＨＳＰのみが、変化される必要がある。同様に、Ｆ１におけるエレメント（要素）ｈが取り除かれると、定義によれば、その鎖の中の全てのＨＳＰは、Ｆ１の１つのツリーの中にある。ｈにおいてルートを有する部分ツリー（サブツリー）におけるＨＳＰのみが、変化される必要があり；また、そのツリーのルートがまた取り除かれるので、そのツリーにおける残りのＨＳＰは、再計算される必要がある。しかし、再計算が必要なＨＳＰのセットは、必ずしも、Ｆ２について同じツリーにあるわけではない。本発明の１つの実施形態において、鎖全体が１度に全て取り除かれる代わりに、取り除かれる鎖の個々のエレメント（要素）は、個々に取り除かれ、同様にして、このエレメントのサブツリーも取り除かれる。
【００７１】
再計算の後に、ｌｉｎｋ＿ｈｓｐｓ（）は、新しいツリー構造における最良の鎖を決定する。このプロセスに対する愚直なアプローチは、ツリーが変化したＨＳＰの全てにアクセスすることが絡むということである。実験的な証拠によると、再計算を必要とするＨＳＰの数は変化したＨＳＰのわずかな部分であるという傾向があるので、このアプローチは、不必要に時間を消費することとなる。より効率的なアプローチでは、各ＨＳＰについてのスコアＳ（ｈ）に基づき、フォレストにおける各ツリーについてヒープ使用する。このヒープによって、このツリーの最もスコアの高い鎖が、Ｏ（１）時間内に決定されることを可能にする。再計算を必要とするＨＳＰのみがアクセスされるので、この総実行時間は、最も悪い場合で、Ｏ（ｒｍ０．５＋ｒｌｏｇｍ）であり、そして、実際には、Ｏ（ｒｌｏｇｍ）であり、ここで、ｒは、再計算の数であり、ｍは、ＨＳＰの数である。実験的な証拠によって、ｒは、実際には、ほぼｍ１．５である。
【００７２】
１つの例において、１．１Ｍｂのクエリーを、６５０Ｍｂの配列データベースに対して実行した。（米国の）全国バイオテクノロジー情報センター（「ＮＣＢＩ」）から利用可能であるＢＬＡＳＴの実装（バージョン２．１．２）は、実行に１７時間を必要とした。対照的に、上述のようなｌｉｎｋ＿ｈｓｐｓ（）の改良型を使用したＢＬＡＳＴの実装は、同じ条件のもと３時間未満で完了した。
【００７３】
上述したように、ハッシュテーブルにおける操作（ハッシュテーブルへの配置およびその繰り返し（ｌｏｏｐｉｎｇ ｏｖｅｒ ｉｔ）は、かなりの量の時間を費やす。これは、短いクエリーについては、特に、そのとおりであり、テーブルにおける僅かなエントリーのみが配置される。実際のところ、ＭｅｇａＢｌａｓｔが多くの小さなクエリーに関してヌクレオチド対ヌクレオチドの検索をより速く提供するように開発された１つの理由は、Ｚｈａｎｇ，Ｚ．，Ｓｃｈｗａｒｔｚ，Ｓ．，Ｗａｇｎｅｒ，Ｌ．ａｎｄ Ｍｉｌｌｅｒ，Ｗ．，Ａ ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｌｉｇｎｉｎｇ ＤＮＡ ｓｅｑｕｅｎｃｅｓ．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｂｉｏｌｏｇｙ，７（１−２）：２０３−２１４（２０００）（これらの全体は、本明細書において、参考として援用される）に記載されている。例えば、以下のようなウェブ上で利用可能ないくつかのスクリプトがまた存在する：クエリーを一緒に「パック」するスクリプト、例えば、クエリーと間で「留意しない」処理を付す（すなわち、ヌクレオチドについては、Ｎ、アミノ酸についてはＸ）スクリプト、単一の検索を実行して、得られた結果に後処理を行い、一体型クエリー内でオリジナルクエリーのオフセットに対して修正を加えるスクリプト。例えば、クエリーＡＣＴＧおよびＧＣＧＣＧが、ＡＣＴＧＮＮＮＮＮＮＮＮＮＧＣＧＣＧとしてパックされ得る。留意しない点は、このクエリーに亘ってヒットが生じる可能性がないとすることである。ＭｅｇａＢｌａｓｔおよびこれらのスクリプトにかかわる問題点は、精度（ａｃｃｕｒａｃｙ）が失われるといことであり、すなわち、その統計値は、単一の長いクエリーと多くの短いクエリーについて相違意味するということである。
【００７４】
１つの好ましい実施形態に従って、Ｐａｒａｃｅｌ ＢＬＡＳＴ Ｑｕｅｒｙ Ｐａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍは、速度の向上を伴って統計学的な妥当性を維持する。１つの実施形態において、このＰａｒａｃｅｌ ＢＬＡＳＴ Ｑｕｅｒｙ Ｐａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍは、同じ時間において複数のクエリーのハッシュを構築することによって動作する。位置のみを含むハッシュテーブルの代わりに、これは、（クエリー番号，クエリーにおける位置）という順列ペアを含む。例えば、表１は、クエリーＱ１（ここで、Ｑ１＝ＭＳＬＰＴ）がハッシュされたときに生成されたハッシュテーブルを含む。さらに仮定したときに、クエリーＱ２＝ＡＬＰＴＶおよびＱ３＝ＶＭＳＬＩＣがハッシュされる。この得られたハッシュテーブルは、表２で示される。
【００７５】
（表２−クエリーＭＳＬＰＴ、ＡＬＰＴＶ、およびＶＭＳＬＩＣに対するクエリーパッキングハッシュテーブル）
【００７６】
【表２】
【００７７】
（並列アーキテクチャにおける実装）
１つの実施形態において、上述のような改良を組み込んだＢＬＡＳＴアルゴリズムの実装は、Ｂｅｏｗｕｌｆ型並列処理アーキテクチャ上で実行される。この実施形態において、このマシンは、データベース検索を高速度のスループットで実行する。クエリーが受信されると、クエリーは、一体型クエリーサイズが予め決定された閾値に到達するまで、一体型クエリーへとパッキングされる。検索されるデータベースは、分割され、そして、このマシン上のプロセッサの各々は、このデータベースの特定の分割された部分についての一体型クエリー検索を取り扱う。好ましい実施形態において、このデータベースは、動的に分割され、各プロセッサは、ほぼ同じ時間の量での検索を完了する。各データベース検索の出力は、一体型クエリーにおいて、ヒットの各々とそのクエリーとを連結する情報にとともに、複数のヒットを含む。ヒットの各々についての対角成分計算は、クエリー特異的であるので、各クエリーのヒットは、ｌｉｎｋ＿ｈｓｐｓ（）を使用して別個に伸長される。１つの実施形態において、各クエリーのヒットは、別個のプロセッサー上で処理され得る。代替的な実施形態において、各クエリーのヒットは、このデータベース検索を実施するために使用される同一のプロセッサ上で伸長される。データベースの分割のために、全ての一体型クエリーのヒットが、見出され、そして、伸長されたとき、分割の中間結果が記憶される。最後には、全てのデータベース分割についての中間結果は、再結合されて、そして、最終的なＢＬＡＳＴレポートがこの一体型クエリーにおける各クエリーについて生成される。１つの好ましい実施形態において、このＢｌａｓｔＭａｃｈｉｎｅは、Ｂｅｏｗｕｌｆ型Ｌｉｎｕｘクラスターであり、マネージャーノードおよび複数のワーカーノードからなる（図２を参照のこと）。各ノードは、Ｐａｒａｃｅｌ ＢＬＡＳＴ、すなわち、最適化したバージョンのＮＣＢＩ ＢＬＡＳＴを実行する。このマネージャーは、ジョブを分割してより小さな部分にし、それらの部分をワーカーに割り当て、それらの結果を回収し、そしてそれらの結果をクライアントに戻すことによって、クライアントＢＬＡＳＴリクエストに応答する。このシステムの多くの困難は、以下にさらに詳細に議論されているような局面（ａｓｐｅｃｔ）を、分割およびスケジュール管理することにある。わずか１個のＣＰＵを有するＢｌａｓｔＭａｃｈｉｎｅｓおよび９２個ものＣＰＵを有するＢｌａｓｔＭａｃｈｉｎｅｓが構築された。１つの実施形態において、各ワーカーノードは、２ＣＰＵ Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩシステムである。
【００７８】
ジョブを分散させるときの、２つの性能に関連する問題は、１）負荷分散（ｌｏａｄ ｂａｌａｎｃｉｎｇ）および２）キャッシングである。負荷分散を例示するために、単一のプロセッサで１００分かかるジョブを５０プロセッサに分散することを仮定する。各プロセッサの負荷が同等であるとすると、これらのジョブは、２分間かかる。あるいは、４９のプロセッサが１分間を必要とする部分を受け取るとすると、最後のプロセッサが５１分間を必要とする部分を受け取る。次いで、問題全体が、５１分間かかるとすると、１つのＣＰＵにおいて必要とされる時間は、大まかに半分である。乏しい負荷分散のために、このジョブが、どんな方法でも、プロセッサの数だけに基いて期待される、５０倍近くの速度向上に到達し得ない。この種の異常な実情を改善するために、ジョブを可能な限り多くの部分に分割することが所望される。どの部分が最も時間を費やすかということを、先見的に知ることはできない（この時間の多くの部分が、ヒットの数に依存し、これは、検索を実行することなしには、知ることはできない）ので，より多くの部分に分割することによって、より速い部分がずっと速く完了することが可能され、従って、これらのプロセッサーは、残りの部分のために使用され得る。小部分の限界において、１つのジョブをこのような小部分へと分解して、それによって、プロセッサの数と同等の実際の速度向上を達成し得ることが望まれている。しかし、実際のところ、各部分に関連する、幾分少量のオーバーヘッドが存在し、そして、この分割がどれ程まで細かい単位であり得るかということに関しては限界が存在する。
【００７９】
直接的なクエリー分割技術は、各クエリーを、その別個のサブジョブに分割することである。ついで、このような部分の各々は、ＢＬＡＳＴアルゴリズムにおいてそれに続く工程で統計値を調整することを必要とせず、独立してスケジュール管理され、そして、異なるプロセッサーに配置され得る。各クエリー部分を独立してスケジュール管理する工程は、正確だが、最適ではないことがわかった。なぜならば、これが、上記のクエリーパッキングアルゴリズムによって提供される最適化したものを損なうためである。そのアルゴリズムは、いかに複数のクエリーが一緒にパックされ得ようとも、速度向上を達成する。そして、Ｐａｒａｃｅｌ Ｂｌａｓｔマネージャーノードは、いくつかの分散工程（ｂａｌａｎｃｉｎｇ）を実行し、一方で、そのマネージャーノードは、可能な限り細かく分割することを必要とし、より良好な付加分散を達成し、そして、より効率的な並列処理（ｐａｒａｌｌｅｌｉｓｍ）を使用し；他方で、そのマネージャーノードは、複数のクエリー配列を一緒に維持して、各部分における速度を最適化することを必要とする。待ち時間またはスループットについての重要性に依存して、かつ含まれるデータの特異性（ｓｐｅｃｉｆｉｃｓ）に依存して、異なったストラテジーが使用され得る。これらのストラテジーは、以下に詳細に議論されている。
【００８０】
上記で議論したように、Ｐａｒａｃｅｌ Ｂｌａｓｔがクエリーを分割するのと同じ方法で、これは、データベースを分割し得る。１つの実施形態において、各データベースＤおよび各クエリーＱについて、このＰａｒａｃｅｌ ＢＬＡＳＴアルゴリズムによって、ＱとＤとの間のアライメントが見出される。しかし、問題点が存在する。アライメントを見出すために、そのデータベース全体における、サイズおよび配列数に依存する統計学的なカットオフが、使用される。１つの実施形態において、強化されたＢＬＡＳＴコードは、プロセスマネージャーアルゴリズムがその情報を各クエリー部分に渡すことを可能にする。アルゴリズムの第２の部分は、同じクエリー部分に対応する全てのデータベース部分を一緒にする。クエリーＱの各々について、このアルゴリズムは、以下で詳細が説明されるように、ＭＥＲＧＥ（Ｄ１，Ｄ２，．．．，Ｄｍ）と呼ばれる関数にある上位ｎのデータベース配列を報告する。不運なことに、この一緒にする工程は、ネイティブＮＣＢＩ ＢＬＡＳＴの順位とは異なる順位を、時折生成し得え、これは、同じスコアを有するアライメントが、決定論的に（ｄｅｔｅｒｍｉｎｉｓｔｉｃａｌｌｙ）ソートされないためである。しかし、結果の質は、同等であり、これは、統計学的に有効なものである。
【００８１】
１つの実施形態において、マージ手順（合わせる手順）は、以下の通りである：データベース部分Ｄ１、Ｄ２、．．．、Ｄｍ、および各データベースについての上位ｎ個のアライメントを与え、全体として、上位ｎ個のアライメントを見つけ出す。好ましい実施形態において、クエリー分割およびデーターベース分割は、相互に独立しているので、両方の最適化は、同時に適用され得る。
【００８２】
データーベース分割の１つの利点は、データベースが、そのノード上のＲＡＭに適合するのに十分な小さい部分に分割され得ることである。これは、以下の２つの利点を提供する：
１．ＢＬＡＳＴアルゴリズムは、データベースが、ディスクからまたはネットワークを超えてデータベースにアクセスするよりもむしろメモリー内にとどまり得る場合に有意により速い様な様式で、コードされ、そして
２．データベース（特に、大規模なもの）を移動し回ることは、コストがかかるので、マネージャーは、同じデータベース部分を同じプロセッサに割り当てるように試み、それによって、有意な速度改善を達成する。
【００８３】
データベースキャッシュ処理もまた、優れた直線的スピードアップを可能にする。基本的に、（メモリーに実装するには大き過ぎるので）ディスクからデータベースをロードしなければならないジョブは、部分に分けられ得、ここで、各部分は、メモリーに実装するために十分に小さい。単一ＣＰＵについての合計時間は、（ＤＢディスクアクセス）＋（計算）となる。Ｎ個のＣＰＵについて、総時間は、１／Ｎ（ＤＢ ＲＡＭアクセス）＋（１／Ｎ）・（計算）になる。ＲＡＭアクセスがディスクアクセスよりずっと速いので、Ｎ個のＣＰＵに対する合計時間は、１つのＣＰＵに対についての時間の１／Ｎ未満であり、おそらくはそれよりずっと少なく、そして速度向上は、超直線的（ｓｕｐｅｒ−ｌｉｎｅａｒ）であり得る。
【００８４】
この効果は、多くの部分に分けられる大きなジョブについて特に著しく、すなわち、第１の部分が、プロセッサの数によってナイーブに（ｎａｉｖｅｌｙ）分割することに基づいたときに予期される速度と同じ速度で実行する。それに引き続く部分は、キャッシュされたデータベースを使用し得、そして、ずっと高速である。従って、全体のジョブ（より長いジョブについて）は、ディスクアクセス時間ではなく、ＲＡＭアクセス時間に向かう傾向がある。これは、ただ、Ｐａｒａｃｅｌ Ｂｌａｓｔマネージャーが同じデータベースを使用する異なるサブジョブを同じプロセッサに割り当てることを試みるので、生じることに注意のこと。
【００８５】
上記分割アルゴリズムが１セットのクエリー配列、または一体型クエリー、および複数の配列を含むデータベースに適用することが理解される。個々の配列は、代表的には、分割されない。しかし、利用可能なゲノム配列を用いて、個々の配列は、多くのメガ塩基長であり得る。１つの実施形態において、このような長い個々の配列を操作するために、Ｐａｒａｃｅｌ Ｂｌａｓｔは、クエリーチョッピング（Ｑｕｅｒｙ Ｃｈｏｐｐｉｎｇ）と呼ばれるアルゴリズムを使用する。
【００８６】
クエリーチョッピングを行うためのナイーブな方法は、長い配列を重なる部分に手動で分割し、そして図３に示されるように別々に各部分を実行する。これは、ＢＬＡＳＴの内部へのアクセスなしで、スクリプトによってなされることさえあり得る。Ｐａｒａｃｅｌ Ｂｌａｓｔのクエリーチョッピングは、重なりゾーンにおけるいくつかの潜在的な問題を正す点で、幾分より精巧である。
【００８７】
図４を参照して、全てのＨＳＰが生成された後、以下の３種類が存在する：重なり合わない領域に完全に含まれるＨＳＰ（ＨＳＰ１）、重なり合う部分に完全に含まれるＨＳＰ（ＨＳＰ２）、および重なり会う部分に部分的に含まれかつ重なり会わない部分に部分的に含まれるＨＳＰ（ＨＳＰ３およびＨＳＰ４）。第１のクラスのＨＳＰは、問題を呈しない。第２のクラスは、２回（左部分にて１回、右部分にて１回）見出される。それらを１回報告するのみという問題以外に、それらは、特別な問題を呈しない。第３のクラスは、少々厄介な問題である。
【００８８】
他の全てに優先する設計上の目標は、チョッピングがなく、そして配列全体が全体として処理された場合に得られる結果と同じ結果を提供することである。図４に示されるように、一部重なりを有するが隣接する部分のなかで十分短く停止する任意のアライメント（例えば、ＨＳＰ３）は、チョッピングが生じなかった場合に、その部分を十分に短く停止する。唯一の問題は、全体の重なりを含むまともなＨＳＰ（例えば、ＨＳＰ４）である。このような（まれな）ＨＳＰは、チョッピングによって中断されるが、重なりの両端（実際には、特定の縁効果が存在するので、重なりのいくらかの距離内にある）でヒットするチョップされた配列において、ＨＳＰとして検出され得る。
【００８９】
Ｐａｒａｃｅｌ ＢＬＡＳＴクエリーチョッピングアルゴリズムは、このようなＨＳＰを検出し、そしてそのＨＳＰに導く元のヒットに戻る。元のヒットは、チョップされないクエリーの状況でＨＳＰに拡張される。この操作はコストがかかるが、これが非常にまれである（重なりに完全にわたるＨＳＰが存在する場合にのみ存在する）ことを注意のこと。１つの好ましい実施形態において、Ｐａｒａｃｅｌ ＢＬＡＳＴは、１０キロ塩基のデフォルトの重なりを使用し、そこで再計算するための時間は、代表的に、クエリーをより忠実に分割し、そしてそれを複数のプロセッサに請け負わせ得ることによって得られる節約と比較して、非常に短い。
【００９０】
本発明の１つの実施形態において、Ｐａｒａｃｅｌ ＢＬＡＳＴは、マネージャーモジュールを含み、これは、ジョブを部分に分割し、各部分を最も利用可能なワーカー（例えば、プロセッサまたはＣＰＵ）に請け負わせ、次いで、部分を再結合する。このマネージメント機能を実行する際に、マネージャーモジュールは、特定の競合する束縛を考慮する。負荷分散の理由のため、できるだけ多くの部分に分割することが最適である。クエリーチョッピングおよびデータベース分割（マージ工程（あわせる工程）を有する）について、過剰な分割は、より多くのマージ（合わせること）を必要とし、従って、非能率的である。クエリー分割について、過剰な分割は、クエリーパッキングによって得られる効率を台無しにする。分割はまた、マシンの数を考慮すべきである。あまりにも少なすぎる部分への分割は、マシンをアイドリングさせ、一方、過剰の分割（マシンよりも多い部分への分割）は、負荷分散を改善することが望ましくあり得る。さらに、ディスクからネットワークを越えて、ワーカーのプロセッサにデータを移動する問題が存在する。十分に大きなデータベースについて、データの移動時間は、有意であり、計算時間を支配し得る。このような場合において、より少ない部分に分割することがより良好であり得る。Ｐａｒａｃｅｌ ＢＬＡＳＴは、これらのスケジューリング問題を扱う良好な（しかし、完全ではない）ジョブを実行するための１セットのヒューリスティックスを使用する。
【００９１】
（実験結果）
上記改善は、独立にまたは集団的に観察され得る。以下に考察される実施例において、全てのＢｌａｓｔＭａｃｈｉｎｅノードは、他の特に述べない限り、２ＧＢのＲＡＭを有する、９３３ＭＨｚで実行するデュアル Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩプロセッサからなった。
【００９２】
（コード最適化、ハッシュテーブルキャッシング、およびクエリーパッキング）
コード最適化の能力を実証するために、データ構造最適化、およびクエリーパッキング、ヒト第２２染色体から取得した５０，０００の２５マー（すなわち、合計１，２５０，０００塩基）のクエリーデータセットを、ＮＣＢＩ（１０，２３９配列、２４，３００，７７４塩基）からのヒト参照配列データベースに対して、実行した。９３３ＭＨｚにおいて実行する１つのＣＰＵ Ｐｅｎｔｉｕｍ（登録商標） ＩＩＩシステムにおいて、ＮＣＢＩ ＢＬＡＳＴは、３時間１６分かかった。同じハードウェアにおいて、Ｐａｒａｃｅｌ ＢＬＡＳＴは、２２分３５秒かかった（８．７倍の速度向上）。
【００９３】
（クエリー分割）
クエリー分割、それ自体は、待ち時間を改善し、スループットを改善しない。しかし、以下に考察されるシステムのベンチマークの全てにおいてある役割を果たす。
【００９４】
（データベース分割）
Ｂａｙｌｏｒからのヒト転写データベースの８分の１（５．６メガ塩基を含む１０，６１０配列）を、ヒトアンサンブルデータベース（４．４ギガ塩基を含む３０，４４５配列）に対して実行した。この検索は、実質的な量のメモリーを必要とした。実際、ＮＣＢＩ ＢＬＡＳＴ２．１．２を、単一のＣＰＵ Ｐｅｎｔｉｕｍ（登録商標）ＩＩＩシステムランのメモリーのアウトで実行し、そして２週間後、失敗する。大規模メモリーにおいて、４ＣＰＵ Ａｌｐｈａ ＥＳ４０システム、ＮＣＢＩ ＢＬＡＳＴ２．１．２は、２１４時間１４分（ほぼ９日）で実行する。３２ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅでは、同じ検索は、たった３時間１７分で完了までで実行する。
【００９５】
（クエリーチョッピング）
クエリーチョッピングの能力を説明するために、全てのヒトＥＳＴを、第２２染色体に対して並置させた。使用されるたＥＳＴデータベースは、３７０万の配列を含み、合計１．８ギガ塩基である。第２２染色体（Ｓａｎｇｅｒ Ｃｅｎｔｒｅから入手される）は、３４．６メガ塩基の単一の配列を含む。このサイズの問題は、代表的なＬｉｎｕｘ ＰＣでのＮＣＢＩ ＢＬＡＳＴで実行され得ない（これは、すぐにメモリーをランアウトし、終わる）。Ｐａｒａｃｅｌ ＢＬＡＳＴのクエリーチョッピングを使用して、検索は、１９分４３秒で、８ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅで実行された。
【００９６】
（Ｃ．ｅｌｅｇａｎｓタンパク質 対 ＮＲ）
目的のいくつかの問題は、従来のコンピューターでの合理的な時間で完了され得ない。例えば、Ｗｏｒｍｐｅｐ１９データベース（Ｃ．ｅｌｅｇａｎｓからの８３０万ペプチドを含む１９，１０５配列を含む）を、ＮＲデータベース（ＮＣＢＩからの非冗長タンパク質配列データベース）に対して検索した。ＮＲは、１億８３００万のペプチドを含む５８２，２９０配列を含む。Ｗｏｒｍｐｅｐ配列のうちの１つが単一の２５，０００ペプチドタンパク質であることが特に注記される。１ＣＰＵシステムにおいて、ＮＣＢＩ ＢＬＡＳＴは、４日後に失敗した（おそらく、配列サイズに関連するメモリー問題に起因する）。Ｐａｒａｃｅｌ ＢＬＡＳＴを用いる３２ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅにおいて、同じ検索は、１時間５７分で完了まで実行した。
【００９７】
（全てのヒトＥＳＴ 対 全ての染色体）
現在までの最も大きな検索実行のうちの１つは、全てのヒトＥＳＴと全てのヒト染色体とのアライメントであった。上記のように、使用されたＥＳＴデータベースは、３７０万配列を含み、合計１．８ギガベースである。完全なセットのヒト染色体（ＵＣＳＣから得られる）は、３，６２６配列を含み、合計３．３ギガベースである。この検索は、クエリーチョッピングなしでは可能でなく、そして上で網羅される他の最適化の全てなしでは、過度に遅い。４８ＣＰＵ ＢｌａｓｔＭａｃｈｉｎｅでのＰａｒａｃｅｌ ＢＬＡＳＴを用いて、８５時間４９分で完了まで実行された。現在、ＥＳＴおよび第２２染色体を用いて実施されるような、本発明者らが、結果を詳細に分析し得るのに十分な、ヒト染色体の大部分の注釈が存在していない。
【００９８】
（結論）
Ｐａｒａｃｅｌ ＢｌａｓｔＭａｃｈｉｎｅは、ゲノムスケールでの相同性検索のためのシステムである。相同性検索の感度および選択性を改善することに焦点を当てるよりもむしろ、以前に可能であったよりも速くそしてより大きなデータについての合理的に良好なジョブをすることを求める。Ｐａｒａｃｅｌ ＢＬＡＳＴは、問題を分割し、そしてできるだけ多くのノードにそれらを請け負わせる、多くの個々の最適化を組み合わせる。各ノードは、ＣＰＵをより効率的に使用するように最適化されたコードを実行する。クエリー分割、データベース分割、クエリーチョッピング、クエリーパッキング、データベースキャッシュ処理、ハッシュテーブルキャッシュ処理、およびアセンブリ最適化の組合せによって、ＢｌａｓｔＭａｃｈｉｎｅが、デスクトップコンピューターよりも、２〜３桁速くなる（実際の数は、問題、およびこれらの最適化が開発され得る程度に依存する）。
【００９９】
アルゴリズムの全てがユーザーに対して透過性である。ユーザーは、ＧＵＩまたはコマンドラインを介してＢＬＡＳＴジョブを入力し、そしてソフトウェアは、自動的に、ユーザのさらなる介入なしで全ての適用可能な最適化を適用する。ＢｌａｓｔＭａｃｈｉｎｅは、数週ではなく、数時間でゲノムスケールの問題を解決する（例えば、ヒト転写データベースとヒトアンサンブルデーターベースとの比較は、ＮＣＢＩ ＢＬＡＳＴ２．１．２を実行するＡｌｐｈａシステムでの９日間と比較して、ＢｌａｓｔＭａｃｈｉｎｅでたった３時間かかった）。さらに、Ｐａｒａｃｅｌ ＢＬＡＳＴは、特定のジョブを自動的に管理可能な部分に分割し、そして従って、他のアーキテクチャー（例えば、全てのヒトＥＳＴを染色体に配置する）では失敗するような検索を完了するように実行する。さらに多くのゲノムスケールのデータセットが利用可能になるにつれて、本発明者らは、この種の最適化ツールが、大規模なデータ分析およびマイニングについてに有用性は増大する。
【０１００】
本発明は、本発明の精神または必須の特徴から逸脱することなく、他の特定の形態で具体化され得る。従って、上記実施形態は、本明細書中に記載される本発明を限定するというよりもむしろ、本発明の例示の全ての局面において考慮されべきである。従って、本発明の範囲は、上記記載によってよりもむしろ、添付の特許請求の範囲によって示され、そして従って、特許請求の範囲に等価な意味および範囲に入る全ての改変は、そのなかに含まれると意図される。さらに、本明細書中に記載される改善が、ＤＮＡおよびペプチドのような生物学的情報の配列に制限されず、任意の種の文字列検索に適用可能であることが企図される。
【図面の簡単な説明】
【０１０１】
【図１】図１は、ハイスコアセグメントペアを表す有向閉路グラフを提供する。
【図２】図２は、本発明の１つの実施形態に従う、ＢｌａｓｔＭａｃｈｉｎｅシステムアーキテクチャの高レベルのブロックダイアグラムを例示する。
【図３】図３は、クエリーチョッピングの図式的表現を例示し、ここで、オリジナルクエリーは、重なりのある（オーバーラップ）サブクエリーへと切断（チョップ）され、これは、次いで、本発明の実施形態に従って、分散され得る。
【図４】図４は、本発明の１つの実施形態に従って、様々なＨＳＰのタイプをクエリーチョッピングすることの図式表現を例示する。
Claims (9)
- 配列データベースに対して複数のクエリー配列を比較するための方法であって、該方法は、以下の工程：
（ａ）該複数のクエリー配列を、一体型クエリー配列に結合する工程；
（ｂ）該データベースの複数の下位区分を決定する工程；
（ｃ）複数の検索を実施する工程であって、ここで、各検索は、該データベースの複数の下位区分のうちの１つに対する該一体型クエリー配列の比較を含み、複数のワードマッチを生成する工程；
（ｄ）工程（ｃ）において生成された複数のワードマッチの長さを伸長し、複数のハイスコアセグメントペアを生成する工程；
（ｅ）上記の複数のハイスコアセグメントペアを結合する工程；および
（ｆ）複数のレーポートを作成する工程であって、各レポートは、複数のクエリー配列のうちの１つに対する最もスコアの高いマッチを示す工程、
を包含する、方法。 - 請求項１に記載の方法であって、前記伸長工程（ｄ）は、以下の工程：
（ｉ）１セットのハイスコアセグメントペアを評価して、第１の基準に従う該セットにおいて最もスコアの高い鎖を決定する工程であって、ここで、該鎖は、ハイスコアセグメントペアにおける該セットのサブセットを含む工程；
（ｉｉ）ハイスコアセグメントペアの該セットから該鎖を取り出す工程；および
（ｉｉｉ）ハイスコアセグメントペアの該セットが無くなるまで、工程（ｉ）および（ｉｉ）を反復する工程、
を包含する、方法。 - 請求項２に記載の方法であって、前記評価工程（ｉ）が、第２の基準に従う再計算を必要としない、前記セットのハイスコアセグメントペアのサブセットを決定する工程を包含する、方法。
- ＢＬＡＳＴアルゴリズムを用いて、データベースにおける配列検索を実行するための方法であって、以下の工程：
（ａ）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルする工程；
（ｂ）該データベースにおける各配列について、閾値Ｔを超えるスコアを有するワードヒットについてスキャンする工程；および
（ｃ）各ワードヒットについて、該ワードヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアペア（ＨＳＰ）を形成する工程、
を使用し、
ここで、改良として、該検索を実施する前に、一体型クエリー配列へと複数のクエリーを結合する工程を包含する、
方法。 - ＢＬＡＳＴアルゴリズムを用いて、データベースにおける配列検索を実行するための方法であって、以下の工程：
（ａ）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルする工程；
（ｂ）該データベースにおける各配列について、閾値Ｔを超えるスコアを有するワードヒットについてスキャンする工程；および
（ｃ）各ワードヒットについて、該ワードヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアセグメントペア（ＨＳＰ）を形成する工程、
を使用し、
ここで、改良として、該検索を実施する前に、該データベースの複数の下位区分を決定する工程を包含する、
方法。 - ＢＬＡＳＴアルゴリズムを用いて、データベースにおける配列検索を実行するための方法であって、以下の工程：
（ａ）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルする工程；
（ｂ）該データベースにおける各配列について、閾値Ｔを超えるスコアを有するワードヒットについてスキャンする工程；および
（ｃ）各ワードヒットについて、該ワードヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアセグメントペア（ＨＳＰ）を形成する工程、
を使用し、
ここで、改良として、該検索を実施する前に、可能な何時においても、ハッシュテーブルが、プロセッサとメモリとの間で往来するのではなく、プロセッサキャッシュに留まるようにコードを再構築する工程を包含する、
方法。 - ＢＬＡＳＴアルゴリズムを用いて、データベースにおける配列検索を実行するための方法であって、以下の工程：
（ａ）クエリー配列から長さｗの高いスコアのワードのリストをコンパイルする工程；
（ｂ）該データベースにおける各配列について、閾値Ｔを超えるスコアを有するワードヒットについてスキャンする工程；および
（ｃ）各ワードヒットについて、該ワードヒットを両方向に伸長して、Ｓ以上のスコアのハイスコアセグメントペア（ＨＳＰ）を形成する工程、
を使用し、
ここで、改良として、該検索を実施する前に、１メガ塩基以上のクエリー配列を、より小さい部分に分割する工程を包含する、
方法。 - 請求項７に記載の方法であって、ここで、前記クエリー配列は、以下の工程：
ａ）該クエリー配列を複数の重なり合う配列へと分割する工程；
ｂ）重なり合う部分の各々が、唯一の重なり合う配列においてのみ含まれるように、該複数の重なり合う配列から、該重なり合う部分を取り除く工程；および
ｃ）除去を受けた部分が、該重なり合う部分の全体に及ぶ任意のＨＳＰを含むか否かを検出する工程であって、そして、該ＨＳＰが検出された場合に、該ＨＳＰを生じるオリジナルヒットを見出し、分割されていないクエリー配列の状況において該ＨＳＰを伸長する、工程
によって、より小さいな部分に分割される、方法。 - データベースにおいて配列検索を実行するためのシステムであって、該システムは、マネージャーノードおよび複数のワーカーノードを備え、ここで、該マネージャーノードは、クライアントステーションおよび該ワーカーノードの各々に作動可能に接続されて、そして、該システムは、請求項１に記載の方法に従って、データベース中の配列検索を実行することが可能である、システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US28846501P | 2001-05-04 | 2001-05-04 | |
| PCT/US2002/014535 WO2002090978A1 (en) | 2001-05-04 | 2002-05-06 | Method and apparatus for high-speed approximate sub-string searches |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2005500594A true JP2005500594A (ja) | 2005-01-06 |
Family
ID=23107215
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002588186A Withdrawn JP2005500594A (ja) | 2001-05-04 | 2002-05-06 | 高速の近似部分文字列検索ための方法および装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6931401B2 (ja) |
| EP (1) | EP1402254A1 (ja) |
| JP (1) | JP2005500594A (ja) |
| CA (1) | CA2446262A1 (ja) |
| WO (1) | WO2002090978A1 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010134694A (ja) * | 2008-12-04 | 2010-06-17 | Fujitsu Ltd | Ｈｓｐ数推定プログラム、ｈｓｐ数推定装置、及びｈｓｐ数推定方法 |
| JP2011204261A (ja) * | 2004-07-02 | 2011-10-13 | Government Of The United States Of America As Represented By The Secretary Of The Navy | リシークエンシング病原体マイクロアレイ |
Families Citing this family (73)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7238491B1 (en) * | 1998-03-27 | 2007-07-03 | Smithkline Beecham Corporation | Pregnane X receptor method |
| US8725418B2 (en) * | 2002-03-25 | 2014-05-13 | Janssen Pharmaceutica, N.V. | Data mining of SNP databases for the selection of intragenic SNPs |
| US6961733B2 (en) | 2003-03-10 | 2005-11-01 | Unisys Corporation | System and method for storing and accessing data in an interlocking trees datastore |
| WO2004084095A1 (ja) * | 2003-03-18 | 2004-09-30 | Fujitsu Limited | 情報検索システム |
| US20050165765A1 (en) * | 2003-03-18 | 2005-07-28 | Fujitsu Limited | Information search system, information search method, information search apparatus, and recording medium to which information search program, is recorded and which can be read by computer |
| US20050053305A1 (en) * | 2003-09-10 | 2005-03-10 | Yadong Li | Systems and methods for implementing a speckle reduction filter |
| US8516004B2 (en) * | 2003-09-19 | 2013-08-20 | Unisys Corporation | Method for processing K node count fields using an intensity variable |
| US7584092B2 (en) * | 2004-11-15 | 2009-09-01 | Microsoft Corporation | Unsupervised learning of paraphrase/translation alternations and selective application thereof |
| US7412385B2 (en) * | 2003-11-12 | 2008-08-12 | Microsoft Corporation | System for identifying paraphrases using machine translation |
| JP2005190248A (ja) * | 2003-12-26 | 2005-07-14 | Toudai Tlo Ltd | 配列探索システムおよび探索プログラム |
| US7340471B2 (en) * | 2004-01-16 | 2008-03-04 | Unisys Corporation | Saving and restoring an interlocking trees datastore |
| US7996419B2 (en) * | 2004-03-31 | 2011-08-09 | Google Inc. | Query rewriting with entity detection |
| US7840547B1 (en) | 2004-03-31 | 2010-11-23 | Google Inc. | Methods and systems for efficient query rewriting |
| US7536382B2 (en) | 2004-03-31 | 2009-05-19 | Google Inc. | Query rewriting with entity detection |
| US7590620B1 (en) | 2004-06-18 | 2009-09-15 | Google Inc. | System and method for analyzing data records |
| US7593923B1 (en) | 2004-06-29 | 2009-09-22 | Unisys Corporation | Functional operations for accessing and/or building interlocking trees datastores to enable their use with applications software |
| US7213041B2 (en) | 2004-10-05 | 2007-05-01 | Unisys Corporation | Saving and restoring an interlocking trees datastore |
| US7716241B1 (en) | 2004-10-27 | 2010-05-11 | Unisys Corporation | Storing the repository origin of data inputs within a knowledge store |
| US7908240B1 (en) | 2004-10-28 | 2011-03-15 | Unisys Corporation | Facilitated use of column and field data for field record universe in a knowledge store |
| US7676477B1 (en) | 2005-10-24 | 2010-03-09 | Unisys Corporation | Utilities for deriving values and information from within an interlocking trees data store |
| US7499932B2 (en) * | 2004-11-08 | 2009-03-03 | Unisys Corporation | Accessing data in an interlocking trees data structure using an application programming interface |
| US7348980B2 (en) | 2004-11-08 | 2008-03-25 | Unisys Corporation | Method and apparatus for interface for graphic display of data from a Kstore |
| US20070162508A1 (en) * | 2004-11-08 | 2007-07-12 | Mazzagatti Jane C | Updating information in an interlocking trees datastore |
| US7418445B1 (en) | 2004-11-08 | 2008-08-26 | Unisys Corporation | Method for reducing the scope of the K node construction lock |
| US7546235B2 (en) * | 2004-11-15 | 2009-06-09 | Microsoft Corporation | Unsupervised learning of paraphrase/translation alternations and selective application thereof |
| US7552046B2 (en) * | 2004-11-15 | 2009-06-23 | Microsoft Corporation | Unsupervised learning of paraphrase/translation alternations and selective application thereof |
| US7409380B1 (en) | 2005-04-07 | 2008-08-05 | Unisys Corporation | Facilitated reuse of K locations in a knowledge store |
| US7734615B2 (en) * | 2005-05-26 | 2010-06-08 | International Business Machines Corporation | Performance data for query optimization of database partitions |
| US7389301B1 (en) | 2005-06-10 | 2008-06-17 | Unisys Corporation | Data aggregation user interface and analytic adapted for a KStore |
| JP4670496B2 (ja) * | 2005-06-14 | 2011-04-13 | 住友電気工業株式会社 | 光受信器 |
| US7509337B2 (en) * | 2005-07-05 | 2009-03-24 | International Business Machines Corporation | System and method for selecting parameters for data mining modeling algorithms in data mining applications |
| US8386463B2 (en) * | 2005-07-14 | 2013-02-26 | International Business Machines Corporation | Method and apparatus for dynamically associating different query execution strategies with selective portions of a database table |
| US20070027860A1 (en) * | 2005-07-28 | 2007-02-01 | International Business Machines Corporation | Method and apparatus for eliminating partitions of a database table from a join query using implicit limitations on a partition key value |
| US7908132B2 (en) * | 2005-09-29 | 2011-03-15 | Microsoft Corporation | Writing assistance using machine translation techniques |
| US8429177B2 (en) * | 2006-02-08 | 2013-04-23 | Yahoo! Inc. | Using exceptional changes in webgraph snapshots over time for internet entity marking |
| US20070214153A1 (en) * | 2006-03-10 | 2007-09-13 | Mazzagatti Jane C | Method for processing an input particle stream for creating upper levels of KStore |
| TW200734894A (en) * | 2006-03-10 | 2007-09-16 | Univ Chung Hua | Virtual tree searcher using parallel tree search method |
| US20070220069A1 (en) * | 2006-03-20 | 2007-09-20 | Mazzagatti Jane C | Method for processing an input particle stream for creating lower levels of a KStore |
| US20080275842A1 (en) * | 2006-03-20 | 2008-11-06 | Jane Campbell Mazzagatti | Method for processing counts when an end node is encountered |
| US7734571B2 (en) * | 2006-03-20 | 2010-06-08 | Unisys Corporation | Method for processing sensor data within a particle stream by a KStore |
| US7689571B1 (en) | 2006-03-24 | 2010-03-30 | Unisys Corporation | Optimizing the size of an interlocking tree datastore structure for KStore |
| US8238351B2 (en) * | 2006-04-04 | 2012-08-07 | Unisys Corporation | Method for determining a most probable K location |
| US7676330B1 (en) | 2006-05-16 | 2010-03-09 | Unisys Corporation | Method for processing a particle using a sensor structure |
| US7725453B1 (en) | 2006-12-29 | 2010-05-25 | Google Inc. | Custom search index |
| US7987185B1 (en) | 2006-12-29 | 2011-07-26 | Google Inc. | Ranking custom search results |
| US8290986B2 (en) * | 2007-06-27 | 2012-10-16 | Yahoo! Inc. | Determining quality measures for web objects based on searcher behavior |
| US20090013033A1 (en) * | 2007-07-06 | 2009-01-08 | Yahoo! Inc. | Identifying excessively reciprocal links among web entities |
| US7885969B2 (en) * | 2007-09-17 | 2011-02-08 | International Business Machines Corporation | System and method for executing compute-intensive database user-defined programs on an attached high-performance parallel computer |
| CN102084357B (zh) * | 2008-07-01 | 2014-06-04 | 富士通株式会社 | 检索装置以及检索方法 |
| US8214350B1 (en) * | 2009-01-02 | 2012-07-03 | Google Inc. | Pre-computed impression lists |
| US10339139B2 (en) | 2010-08-16 | 2019-07-02 | Cornell University | Computer system and methods for performing data-driven coordination |
| US10068054B2 (en) | 2013-01-17 | 2018-09-04 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods executed on an integrated circuit processing platform |
| US9792405B2 (en) | 2013-01-17 | 2017-10-17 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods executed on an integrated circuit processing platform |
| US9679104B2 (en) | 2013-01-17 | 2017-06-13 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods executed on an integrated circuit processing platform |
| US10847251B2 (en) | 2013-01-17 | 2020-11-24 | Illumina, Inc. | Genomic infrastructure for on-site or cloud-based DNA and RNA processing and analysis |
| US10691775B2 (en) | 2013-01-17 | 2020-06-23 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods executed on an integrated circuit processing platform |
| US9697327B2 (en) | 2014-02-24 | 2017-07-04 | Edico Genome Corporation | Dynamic genome reference generation for improved NGS accuracy and reproducibility |
| US10006910B2 (en) | 2014-12-18 | 2018-06-26 | Agilome, Inc. | Chemically-sensitive field effect transistors, systems, and methods for manufacturing and using the same |
| US10429342B2 (en) | 2014-12-18 | 2019-10-01 | Edico Genome Corporation | Chemically-sensitive field effect transistor |
| US9618474B2 (en) | 2014-12-18 | 2017-04-11 | Edico Genome, Inc. | Graphene FET devices, systems, and methods of using the same for sequencing nucleic acids |
| US10020300B2 (en) | 2014-12-18 | 2018-07-10 | Agilome, Inc. | Graphene FET devices, systems, and methods of using the same for sequencing nucleic acids |
| US9859394B2 (en) | 2014-12-18 | 2018-01-02 | Agilome, Inc. | Graphene FET devices, systems, and methods of using the same for sequencing nucleic acids |
| US9857328B2 (en) | 2014-12-18 | 2018-01-02 | Agilome, Inc. | Chemically-sensitive field effect transistors, systems and methods for manufacturing and using the same |
| EP3329491A2 (en) | 2015-03-23 | 2018-06-06 | Edico Genome Corporation | Method and system for genomic visualization |
| US20170270245A1 (en) | 2016-01-11 | 2017-09-21 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods for performing secondary and/or tertiary processing |
| US10068183B1 (en) | 2017-02-23 | 2018-09-04 | Edico Genome, Corp. | Bioinformatics systems, apparatuses, and methods executed on a quantum processing platform |
| WO2017201081A1 (en) | 2016-05-16 | 2017-11-23 | Agilome, Inc. | Graphene fet devices, systems, and methods of using the same for sequencing nucleic acids |
| US10600499B2 (en) | 2016-07-13 | 2020-03-24 | Seven Bridges Genomics Inc. | Systems and methods for reconciling variants in sequence data relative to reference sequence data |
| US11392600B2 (en) | 2016-09-22 | 2022-07-19 | Visa International Service Association | Techniques for in memory key range searches |
| CN107766400A (zh) * | 2017-05-05 | 2018-03-06 | 平安科技（深圳）有限公司 | 文本检索方法及系统 |
| CN110134695B (zh) * | 2019-05-21 | 2022-08-16 | 电子科技大学 | 一种面向流水线结构化数据查询的数据库智能分区方法 |
| CN118715566A (zh) | 2022-03-08 | 2024-09-27 | 因美纳有限公司 | 多通道软件加速基因组读段映射引擎 |
| CN115718750B (zh) * | 2022-11-25 | 2025-09-02 | 天津津航计算技术研究所 | 一种基于Cache的多核DSP并行编程优化方法 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6223186B1 (en) * | 1998-05-04 | 2001-04-24 | Incyte Pharmaceuticals, Inc. | System and method for a precompiled database for biomolecular sequence information |
| US6112288A (en) * | 1998-05-19 | 2000-08-29 | Paracel, Inc. | Dynamic configurable system of parallel modules comprising chain of chips comprising parallel pipeline chain of processors with master controller feeding command and data |
| US6421613B1 (en) * | 1999-07-09 | 2002-07-16 | Pioneer Hi-Bred International, Inc. | Data processing of the maize prolifera genetic sequence |
| AU6611900A (en) * | 1999-07-30 | 2001-03-13 | Agy Therapeutics, Inc. | Techniques for facilitating identification of candidate genes |
| US6691109B2 (en) * | 2001-03-22 | 2004-02-10 | Turbo Worx, Inc. | Method and apparatus for high-performance sequence comparison |
-
2002
- 2002-05-06 CA CA002446262A patent/CA2446262A1/en not_active Abandoned
- 2002-05-06 WO PCT/US2002/014535 patent/WO2002090978A1/en not_active Ceased
- 2002-05-06 JP JP2002588186A patent/JP2005500594A/ja not_active Withdrawn
- 2002-05-06 US US10/139,905 patent/US6931401B2/en not_active Expired - Fee Related
- 2002-05-06 EP EP02725964A patent/EP1402254A1/en not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2011204261A (ja) * | 2004-07-02 | 2011-10-13 | Government Of The United States Of America As Represented By The Secretary Of The Navy | リシークエンシング病原体マイクロアレイ |
| JP2010134694A (ja) * | 2008-12-04 | 2010-06-17 | Fujitsu Ltd | Ｈｓｐ数推定プログラム、ｈｓｐ数推定装置、及びｈｓｐ数推定方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US20030033279A1 (en) | 2003-02-13 |
| EP1402254A1 (en) | 2004-03-31 |
| WO2002090978A1 (en) | 2002-11-14 |
| US6931401B2 (en) | 2005-08-16 |
| CA2446262A1 (en) | 2002-11-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2005500594A (ja) | 高速の近似部分文字列検索ための方法および装置 | |
| Holley et al. | Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs | |
| US7231390B2 (en) | Apparatus and method for providing sequence database comparison | |
| Jacob et al. | Mercury BLASTP: Accelerating protein sequence alignment | |
| Krishnamurthy et al. | Biosequence similarity search on the Mercury system | |
| US7761462B2 (en) | Searching queries using database partitioning | |
| US7917299B2 (en) | Method and apparatus for performing similarity searching on a data stream with respect to a query string | |
| US20080133474A1 (en) | Bioinformatics computation using a maprreduce-configured computing system | |
| US20160019339A1 (en) | Bioinformatics tools, systems and methods for sequence assembly | |
| Buhler et al. | Mercury BLASTN: Faster DNA sequence comparison using a streaming hardware architecture | |
| US11580103B2 (en) | System and method for disjunctive joins using a lookup table | |
| Cui et al. | On efficient external-memory triangle listing | |
| US20220391390A1 (en) | System and method for disjunctive joins | |
| Jalili et al. | Next generation indexing for genomic intervals | |
| Langarita et al. | Compressed sparse FM-index: Fast sequence alignment using large K-steps | |
| Deshpande et al. | A platform for biological sequence comparison on parallel computers | |
| Cui et al. | Improving I/O complexity of triangle enumeration | |
| Xiao et al. | K-mer Counting: memory-efficient strategy, parallel computing and field of application for Bioinformatics | |
| KR20040036691A (ko) | 분산 컴퓨팅 환경에서의 유전자 및 단백질 유사서열 검색시스템 및 그 방법 | |
| US20020138464A1 (en) | Method and apparatus to index a historical database for efficient multiattribute SQL queries | |
| Xu et al. | GraphCP: An I/O-efficient concurrent graph processing framework | |
| Aziz et al. | Parallel generalized suffix tree construction for genomic data | |
| AU2002256495A1 (en) | Method and apparatus for high-speed approximate sub-string searches | |
| US12067014B2 (en) | Methods and systems for performing a vectorized delete in a distributed database system | |
| Schatz | High performance computing for DNA sequence alignment and assembly |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20050802 |