ESTをヒトゲノムに合わせるための高速で敏感なアルゴリズム

発現したシーケンスタグ（EST）の成長セットを、新しく配列決定されたヒトゲノムと整列する必要があります。ただし、この問題は、真核生物遺伝子のエクソン/イントロン構造と、ESTのヌクレオチドを誤解し、数百万の繰り返しシーケンスがゲノムシーケンスで複雑になっています。この問題を解決するために、動的プログラミングを使用するアルゴリズムが提案されています。ただし、実際には、これらのアルゴリズムには膨大な量の処理時間が必要です。これらの古典的なDPアルゴリズムの計算効率を改善するために、Lookup-Tableを完全に利用して特定のDNA配列内のESTの開始点とエンドポイントを効率的に検出し、その後エクソンとイントロンを迅速に識別するソフトウェアを開発しました。さらに、すべてのスプライスサイトの位置は、高い計算効率を保持しながら、高い感度と精度で正しく計算する必要があります。この目標は、ESTのヌクレオチドとゲノムの反復配列を誤解しているため、実際に達成するのは困難です。それにもかかわらず、この問題を効果的に解決する2つのヒューリスティックを提示します。実験結果は、我々の手法がSIM4やBLATなどの一般的なツールと比較して全体的な計算時間を数桁改善し、同時に文書化された遺伝子のクリーンなデータセットに対する高い感度と精度を達成することを確認します。

There is a pressing need to align the growing set of expressed sequence tags (ESTs) with the newly sequenced human genome. However, the problem is complicated by the exon/intron structure of eukaryotic genes misread nucleotides in ESTs, and the millions of repetitive sequences in genomic sequences. To solve this problem, algorithms that use dynamic programming have been proposed. In reality, however, these algorithms require an enormous amount of processing time. In an effort to improve the computational efficiency of these classical DP algorithms, we developed software that fully utilizes lookup-tables to detect the start- and endpoints of an EST within a given DNA sequence efficiently, and subsequently promptly identify exons and introns. In addition, the locations of all splice sites must be calculated correctly with high sensitivity and accuracy, while retaining high computational efficiency. This goal is hard to accomplish in practice, due to misread nucleotides in ESTs and repetitive sequences in the genome. Nevertheless, we present two heuristics that effectively settle this issue. Experimental results confirm that our technique improves the overall computation time by orders of magnitude compared with common tools, such as SIM4 and BLAT, and simultaneously attains high sensitivity and accuracy against a clean dataset of documented genes.