配列分類アルゴリズム
DNA配列を分類するために、その配列内のすべてのk-mersをK(S)と表記されるセットに収集します。 次に、以下に説明するアルゴリズムを使用して、Ｋ（複数可）の各ｋ−ｍｅｒを、そのＫ−ｍｅｒを含むすべてのゲノムのＬＣＡ分類群にマッピングする。 分類木の各ノードは、そのノードに関連付けられた分類群にマップされたK(S)内のk-mersの数で重み付けされます。 次に、パスに沿ったすべてのノード重みの合計を計算することによって、分類ツリー内の各ルートからリーフへの(RTL)パスがスコア化されます。 分類ツリー内の最大スコアリングRTLパスは分類パスであり、Sにはその葉に対応するラベルが割り当てられます（複数の最大スコアリングパスがある場 図1に示すこのアルゴリズムを使用すると、クラーケンはシーケンス内の各k-merを別々の証拠とみなし、必要に応じて矛盾する証拠を解決しようとします。 Kの適切な選択のために、ほとんどのk-mersは単一の種に一意にマッピングされ、分類プロセスが大幅に簡素化されることに注意してください。 K(S)のk-mersのどれもゲノムで見つけられない順序はこのアルゴリズムによって分類されないままにされます。
分類ツリーにおけるRTLパススコアリングの使用は、分類される配列とゲノムの任意のライブラリに存在する配列との間の必然的な違いを考慮して必 そのような相違は、ｋの大きな値についてさえ、ライブラリー中に存在するが、真の供給源種から遠く離れた種に関連するｋ−ｍｅｒをもたらすことができる。 分類ツリー内のさまざまなRTLパスをスコアリングすることにより、これらの違いを補償し、シーケンス内の少数のk-mersがシーケンスに誤った分類ラベルを割
データベース作成
クラーケンの分類アルゴリズムを効率的に実装するには、事前に計算されたデータベースを照会することによって、k-mersの分類群へのマッ クラーケンは、ゲノム配列のライブラリの選択から始まる、マルチステップのプロセスを介して、このデータベースを作成します。 Krakenには、National Center for Biotechnology Information（NCBI）RefSeqデータベースの完成した微生物ゲノムに基づいたデフォルトのライブラリが含まれていますが、個々のユーザーが必要に応じてライブラ
ライブラリが選択されたら、Jellyfishマルチスレッドk-merカウンタを使用して、ライブラリ内のすべての異なる31-merを含むデータベースを作成します。 データベースが完成すると、k-mersカウントをデータベースファイルに格納するために使用される4バイトのスペースは、代わりにK-mersのlca値の分類学的ID番号を格納するためにKrakenによって使用される。 クラゲによってデータベースが作成された後、ライブラリ内のゲノム配列は一度に一つずつ処理されます。 各シーケンスについて、それに関連付けられた分類群は、シーケンス内のすべてのk-mersの格納されたLCA値を設定するために使用されます。 配列が処理されると、配列からのk-merのLCA値が以前に設定されている場合、格納された値と現在の配列の分類群のLCAが計算され、そのLCAがk-merに格納され 分類群情報は、ＮＣＢＩ分類データベースから取得される。
データベース構造と検索アルゴリズム
Krakenは非常に頻繁に隣接するk-merを照会した直後にデータベースクエリとしてk-merを使用し、隣接するk-merはかなりの量のシーケンスを共有するため、minimizerの概念を利用して類似するk-merをグループ化します。 この概念の我々の適用を説明するために、我々はここでは、dna配列Sの正準表現をsの辞書的に小さいとSの逆補体として定義します。 長さＭのｋ-ｍｅｒの最小化器を決定するために，ｋ-ｍｅｒ内のすべてのＭ-ｍｅｒの正準表現を考慮し，それらのｍ-ｍｅｒの中で辞書的に最小のものをｋ-ｍｅｒの最小化器として選択した。 実際には、隣接するk-mersは、多くの場合、同じミニマイザを持つことになります。
クラーケンのデータベースでは、同じミニマイザを持つすべてのk-mersは連続して格納され、それらの標準表現の辞書編集順にソートされます。 K-mer Rのクエリは、rのminimizerを使用してk-merが格納されるデータベース内の位置をインデックスで検索し、その領域内でバイナリ検索を実行することで処理できます(図5)。 隣接するk-mersは同じミニマイザを持つことが多いため、連続する二つのクエリ間で検索範囲が同じことが多く、最初のクエリでの検索では、第二のクエリで使用されるCPUキャッシュにデータを取り込むことができることがよくあります。 この方法では、後続のクエリでメモリアクセスがRAMではなくCPUキャッシュ内のデータにアクセスできるようにすることで、後続のクエリがそうでな データベース内のk-mersの各グループのオフセットを含むインデックスには、8×4Mバイトが必要です。 たとえば、MiniKrakenを作成する際には、データベースの合計サイズが4GB以下になるように13bpミニマイザを使用しました。
クラーケンのデータベース構造。 データベースに対して照会される各k-merには、その最小化子である特定の部分文字列があります。 データベース内のk-merを検索するために、同じミニマイザを持つk-merを含むデータベース内の位置が検査されます。 これらの位置は、k-merのminimizer(オレンジ)と次の可能なminimizer(青)を持つレコードの開始位置のminimizer offset配列を調べることによってすぐに見つけられます。 指定されたミニマイザに関連付けられたレコードの範囲内で、レコードはそのk-mersの辞書式順序でソートされ、この範囲でのバイナリ検索を使用してクエリを完了できるようになります。
Krakenの実装では、上記の構造と検索アルゴリズムをさらに最適化しました。 第一に、Ｒｏｂｅｒｔｓらによって指摘されたように。 、M-mersの単純な辞書編集的順序付けは、低複雑度M-mersを過剰に表す最小化子の歪んだ分布をもたらす可能性があります。 Krakenでは、このようなバイアスは多くの大きな検索範囲を作成し、検索に多くの時間を必要とします。 最小化子のより均一な分布を作成する（したがって検索を高速化する）ために、排他的論理和（XOR）演算を使用して、辞書編集順序を使用してM-merを互いに比較する前に、各M-merの正規表現のビットの半分を切り替えます。 このXOR演算は、標準的な順序付けを効果的にスクランブルし、低複雑さの最小化に向けた大きなバイアスを防ぎます。
また、Krakenのクエリをより速くするために、クエリ間で検索範囲が同じであることが多いという事実を利用します。 クエリを実行するたびにminimizerを計算するのではなく、最初に前の範囲を検索します。 クエリされたk-merがこの範囲で見つかった場合、クエリはすぐに戻ることができます。 K-merのminimizerが最後に照会されたk-merのminimizerと同じである場合、minimizerの検索スペースがk-merを持たないことが示されているため、クエリは失敗します。 ミニマイザが変更された場合にのみ、Krakenは検索範囲を調整し、k-merを再度検索する必要があります。
シミュレートされたメタゲノムの構築
HiSeqおよびMiSeqメタゲノムは、20セットの細菌全ゲノムショットガンリードを使用して構築されました。 これらの読み取りは、GAGE-Bプロジェクトの一部として、またはNCBI Sequence Read Archiveのいずれかで見つかりました。 各メタゲノムには、10個のゲノムからの配列が含まれています(追加ファイル1:表S1)。 これらのメタゲノムのそれぞれの10,000および1000万の読み取りサンプルの両方について、それらの配列の10％が10成分ゲノムデータセットのそれぞれから選 すべての配列をトリミングして、低品質の塩基およびアダプター配列を除去した。
これら二つのメタゲノムの構成は、私たちの分類器に一定の課題を提起します。 例えば、Hiseqメタゲノムに含まれるPelosinus fermentansは、RefSeq complete genomesデータベースにはPelosinusゲノムが存在しないため、kraken（または以前に記載されている他の分類器のいずれか）によって属レベルで正しく同定することはできないが、Kraken-GBのデータベースにはp.fermentansの六つの系統を含む七つのゲノムがある。 同様に、私たちのMiSeqメタゲノムでは、プロテウス尋常性は、クラーケンのデータベース内の唯一のプロテウスゲノムが単一のプロテウスミラビリスゲノムであるため、属レベルで誤って分類されることが多い。 Kraken-GBのデータベースにはさらに五つのプロテウスゲノムが存在し、Kraken-GBはその属からより良い読み取りを分類することができます。 さらに、MiSeqメタゲノムには、腸内細菌科（Citrobacter、Enterobacter、Klebsiella、Proteus、Salmonella）の五つのゲノムが含まれています。 この科の属間の高い配列類似性は、どの分類器でも属間の区別を困難にする可能性がある。
simBA-5メタゲノムは、RefSeqの完全な細菌および古細菌ゲノムのセットからの読み取りをシミュレートすることによって作成されました。 これらのゲノムからのレプリコンは、属ランクに関連付けられたエントリを持つ分類群に関連付けられている場合に使用され、607属からのレプリコンのセットが得られた。 次に、Mason read simulatorとIlluminaモデルを使用して、これらのゲノムから1000万の100bp読み取りを生成しました。 まず、0.1％のSNP率と0.1％のindel率（両方のデフォルトパラメータ）を使用して、各種のシミュレートされたゲノムを作成し、そこから読み取りを生成しました。 シミュレーションされた読み取りでは、既定の不一致率とインデル率に5を掛け、平均不一致率は2%(読み取りの開始時の1%から終了時の6%まで)、インデル率は1%(挿入確率0.5%、削除確率0.5%)となりました。 SimBA-5メタゲノムの場合、10,000個の読み取りセットは、10万個の読み取りセットのランダムサンプルから生成されました。
精度と速度の評価
PhymmBLとNBCの予測の分類情報を自動化して簡単に決定できる最低レベルであった属レベルで精度を測定することにしました。 （これは、PhymmBLとNBCが結果を報告する方法によるものです）。 いくつかのゲノムは、すべての七つのランク（種、属、家族、順序、クラス、門、王国）で分類学的エントリを持っていないので、我々はa/Bとして属レベルの感度を定義し、aはそのランクで正しく分類された割り当てられた属を持つ読み取りの数であり、Bは割り当てられた属を持つ読み取りの総数である。 他の分類学的ランクについても同様に感度を定義した。
クラーケンは種より上のレベルで読み取りを分類する可能性があるため、その精度を測定するには、種をまったく割り当てない間に正しい属を割り当 ここで、Cは測定されたランクの正しい分類群以下にラベル付けされた読み取りの数、Dは測定されたランク以下にラベル付けされた読み取りの数、Eは測定されたランクの上に誤ってラベル付けされた読み取りの数です。 例えば、ｅｓｃｈｅｒｉｃｈｉａ ｃｏｌｉとして標識されるべき読取Ｒが与えられると、Ｒをｅ．ｃｏｌｉ、Ｅ．ｆｅｒｇｕｓｏｎｉｉまたはＥｓｃｈｅｒｉｃｈｉａとして標識することは、属レベルの精度を改善するであろう。 Enterobacteriaceae（正しい家族）またはProteobacteria（正しい門）のラベルは、属レベルの精度には影響しません。 Bacillus（誤った属）またはFirmicutes（誤った門）のRのラベルは、属レベルの精度を低下させるでしょう。
PhymmBLの精度を評価する際に、開発者のアドバイスに従って、比較のために属信頼しきい値を選択しました。 我々は3,333 31の異なる属をカバーするシミュレートされた媒体複雑性（simMC）データセットから読み取りを選択しました。 SimMCセット内のSangerシーケンスデータからの短い読み取りをシミュレートするために、各読み取りから最後の100bpを選択しました。 次に、これらの100bp読み取りに対してPhymmBLを実行し、属レベルの感度とphymmblの予測の精度を0から1までの属信頼しきい値で0.05単位で評価しました。 我々は、0.65のしきい値は、0.60と0.70も0内のFスコアを有すると、最高のFスコア（感度と精度の高調波平均）をもたらしたことがわかりました。最大の5パーセントポイント（追加ファイル1：テーブルS2）。 したがって、比較では0.65属信頼しきい値を使用しました。 閾値の選択は、ユーザの個々のニーズに依存するので、ある程度は任意であるが、この方法で選択された閾値は、閾値が全くないよりも、Ｋｒａｋｅｎのような選択的分類器とのより適切な比較を提供する。
PhymmblがアライメントステップにMegablastを使用しているため、Phymmblが生成したログデータから、Megablastを分類器として使用したときの時間と精度の結果が得られました。 Megablastを使用して分類学的ラベルを読み取りに割り当てるとき、最初に報告されたアライメントに関連付けられた分類群を使用しました。 Megablastはデフォルトのオプションで実行されました。
各プログラム(NBCを除く)のシングルスレッド操作を使用して速度を評価しました。 PhymmBLはblastnプログラムへの呼び出しが二つの代わりに一つのスレッドを使用するように変更されました。 NBCは、そのゲノムライブラリ内のゲノムの互いに素なセット上で動作する36の同時プロセスで実行され、分類器の合計時間は、各ゲノムの減圧とスコー 壁時計の時間は、すべての分類器のために記録されました。 Krakenを他の分類器と比較する際に、BLAST+2.2.27、PhymmBL4.0、NBC1.1、およびMetaPhlAn1.7.6を使用しました。 分類器はすべて同じコンピュータ上で実行され、48個のAMD Opteron6172 2.1GHz Cpuと252GBのRAMを搭載し、Red Hat Enterprise Linux5を実行していました。 速度評価に使用されたデータセットには、Kraken（およびその変種）およびMetaPhlAn以外のすべてのプログラムでそれぞれ10,000個の読み取りがあり、10,000,000個の読み取りデー これらの高速プログラムでは、プログラムの実行中に行われる初期および最終操作の影響を最小限に抑えるために、より高い読み取り番号が使用さ
クラーケンは、分類前にデータが物理メモリにあることを確認するために明示的に操作を実行する唯一のプログラムですが、すべてのプログラムが同様の方法で評価されることを確認したいと考えていました。 速度を評価するとき、各プログラムのために、我々はすべてのデータベースファイルを読みます（例えば PHYMMBL用のIMMファイルとBLASTデータベース、NBC用のk-mer frequency lists、MetaPhlAn用のBowtie index）は、データベースの内容をオペレーティングシステムのキャッシュ（物理メモリに格納されている）に配置するために、プログラムを実行する前にメモリに三回入れられる。
データベースサイズの削減
MiniKrakenの結果のために4GBのデータベースを生成するために、標準のKrakenデータベースの19レコードのすべてのブロックの最初の18を削除し 19の縮小係数は、4GB未満にサイズを縮小する最小の整数係数であり、多くの一般的なパーソナルコンピュータのメモリに容易に収まるサイズであった。 より多くのRAMを使用できるユーザーの場合、Krakenはより小さな縮小係数を使用することができ、感度が向上します。
ドラフトゲノムの使用
Kraken-GBデータベースを構築する際、両端に既知のアダプター配列とのいくつかの連続があることに気付きました。 その後のテストでは、我々はまた、大量のヒト配列を有するサンプル中のいくつかの配列が一貫してこのデータベースによって誤分類されたことを発見し、汚染がドラフトゲノムに存在する可能性が高いと結論づけるために私たちをリードしています。 この汚染に対抗するために、我々は、既知のアダプターシーケンスからのそれらのk-mersだけでなく、ドラフト連続のそれぞれから最初と最後の20k-mersをデータベースか これにより分類が改善されたが、誤分類の問題は解消されなかった。 このため、ドラフトゲノムがKrakenデータベースで使用されている場合、ゲノムライブラリから汚染配列を除去するために非常に厳しい措置を使用すべきであると考えている。
クレード排除実験
クレード排除実験のためのsimBA-5データセットを再分析したとき、測定されたランクと除外されたランクの特定のペアには、いくつかのリ 読み取りの起源が測定されたランクまたは除外されたランクのいずれかで分類学的エントリを欠いていた場合、その特定の実験には使用されません
さらに、私たちのデータベースに記載されている少なくとも二つの他の分類群（除外されたクレードを除く）が除外されたランクで測定されたランクで起源の分類群のクレードを共有しない限り、読み取りは実験では使用されませんでした。 例えば、g属からの読み取りは、クラスランクでの精度を測定し、gのホームクラスがクラーケンのゲノムライブラリにゲノムを持つ少なくとも二つの他の属を持っていない限り、属ランクを除く実験では使用されない。 このフィルタリング手順がなければ、クラス内の唯一の属であったときに属が除外された場合、Krakenはそのクラスのデータベース内のすべてのエントリも これは、PhymmBLを評価するために使用された同様の実験で取られたのと同じアプローチです。
ヒトマイクロバイオームデータ分類
ヒトマイクロバイオームプロジェクトのデータを、完全なRefSeq細菌、古細菌、ウイルスゲノムからなるKrakenデータベースとGrch37ヒトゲノムからなるKrakenデータベースを使用して分類しました。 NCBI Sequence Read Archiveから三つのアクセッション（SRS019120、SRS014468およびSRS015055）のシーケンスを取得し、各アクセッションには二つのランが提出されました。 すべての読み取りは、低品質の塩基とアダプターシーケンスを削除するためにトリ Kronaは、すべての分類学的分布プロットを生成するために使用されました。
シーケンスはすべてペアの読み取りであったため、それらの間に’NNNNN’のシーケンスと一致を連結することによって、読み取りを結合しました。 Krakenはあいまいなヌクレオチドを持つk-mersを無視するため、これらの’N’文字にまたがるk-mersは分類に影響しません。 この操作により、Krakenはメイトを別々に分類するのではなく、読み取りのペアを単一のユニットとして分類することができました。
