大量メタゲノム情報に対するアミノ酸配列相同性検索の高速化

Material type: 博士論文

Author: 鈴木, 脩司ほか

Publisher: -

Publication date: 2015-03

Material Format: Digital

Capacity, size, etc.: -

Name of awarding university/degree: 東京工業大学,博士（工学）

View All

Notes on use

Note (General)：: 本論文は大量なデータに対するメタゲノム解析を実行可能とすることを目的として，(1)高速なアミノ酸配列相同性検索アルゴリズムの提案，(2)graphic processing unit(GPU)による高速化，(3)大規模計算機を利用した並列実行について報告する．類似したアミノ酸配列を持つタンパク質同...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Tokyo Tech Research Repository
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
Tokyo Tech Research Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 博士論文
Title: 大量メタゲノム情報に対するアミノ酸配列相同性検索の高速化
Author/Editor: 鈴木, 脩司
Suzuki, Shuji
Author Heading: 鈴木, 脩司
Suzuki, Shuji
Publication Date: 2015-03
Publication Date (W3CDTF): 2015-03
Alternative Title: Faster Protein Sequence Homology Searches for Large-scale Metagenomic Data
Degree grantor/type: 東京工業大学
Date Granted: 2015-03-26
Dissertation Number: 甲第9884号
Degree Type: 博士（工学）
Text Language Code: eng
Subject Heading: 文字列検索
string search
配列相同性検索
sequence homology search
GPGPU
メタゲノミクス
metagenomics
Target Audience: 一般
Note (General): 本論文は大量なデータに対するメタゲノム解析を実行可能とすることを目的として，(1)高速なアミノ酸配列相同性検索アルゴリズムの提案，(2)graphic processing unit(GPU)による高速化，(3)大規模計算機を利用した並列実行について報告する．類似したアミノ酸配列を持つタンパク質同士には進化的な関係があり，互いによく似た機能を持つことが知られている．このため，類似した配列の情報を用いることでタンパク質の機能を予測することができ，クエリとなるタンパク質のアミノ酸配列と類似する配列を巨大なデータベースの中から見つけ出すアミノ酸配列相同性検索は，生命情報解析の基礎となる手法となっている．近年，DNA配列を読み取る機器であるDNAシーケンサの改良が進んだことにより，短時間に大量の短いDNA配列断片を得ることができるようになった．このため，大量の配列情報を利用した解析を行いたいという要求が高まっている．しかし，微生物の集団から培養を経ずに直接DNA配列を読み取って解析するメタゲノム解析の場合，最新のDNAシーケンサが出力するデータがあまりにも大量であるため，従来用いられてきた検索精度の高いアミノ酸配列相同性検索であるBLASTXでは，多くの処理時間が必要となる．このため，アミノ酸配列相同性検索の高速化が喫緊の課題となっている． (1)の高速なアミノ酸配列相同性検索アルゴリズムの提案では，suffix arrayによる可変長文字列比較を用いたアルゴリズムとデータベースの部分文字列クラスタ情報を用いたアルゴリズムを提案した．Suffix arrayによる可変長文字列比較を用いたアルゴリズムでは，文字列間の類似度指標を基準にしてクエリの部分文字列毎に検索すべき対象文字列の長さを変更し，BLASTXよりも平均的に長い部分文字列を高速に検索する．さらに，クエリとデータベースの両方でデータ構造としてsuffix arrayを用いることで，複数回出現する部分文字列に関してはまとめて検索を行う．このアルゴリズムをGHOSTXとして実装し，典型的な口腔内や土壌のメタゲノムのデータを用いてBLASTXと比較したところ最大約165倍の速度向上が得られることを示した．また，データベースが年々巨大化しているのに伴い冗長な部分文字列が増加している．この冗長な部分文字列に対して効率的なアミノ酸配列相同性検索を行うために，データベースの部分文字列を予めクラスタリングしておき，このクラスタ情報と，文字列間距離に関する三角不等式を利用して詳細なスコア計算を行う回数を削減して高速化するアルゴリズムを提案した．このアルゴリズムをGHOSTZとして実装し，実際のメタゲノムデータを用いてGHOSTXと比較したところ最大約2倍の速度向上が得られることを示した．高速なアミノ酸配列相同性検索アルゴリズムの提案に加え，(2)のGPUによる高速化では，GHOSTZのアルゴリズムを基にしてGPUを用いて検索を行うGHOSTZ-GPUを開発した．GHOSTZ-GPUはGPUのメモリアクセスの最適化やCPUとGPUの非同期処理の利用により，さらなる高速化を行い，12 CPU threadsと3 GPUsを利用した場合，GHOSTZの12 CPU threads利用時よりも最大約7倍の速度向上が得られることを実際のメタゲノムデータを用いて示した．また，(3)の大規模計算機を利用した並列実行では，Message Passing Interface(MPI)を利用し，提案した高速なアミノ酸配列相同性検索を複数ノード上で実行可能とした．実際のメタゲノムデータを用いてTSUBAME2.5の128ノードを利用して実験したところ，BLASTXをMPIによって並列実行するmpiBLASTと比べ，GHOSTXをMPIによって並列実行するGHOST-MPは約89倍の速度向上が得られることを示した．これにより，TSUBAME2.5や「京」などのスーパーコンピュータを利用し，大規模なデータを利用した高速なアミノ酸配列相同性検索が実行可能となった．本研究により最新のDNAシーケンサが出力する全データを利用した大規模なメタゲノム解析が可能となり，環境中の微生物の関係などを詳細に解析するための新たな解析支援ツールとして広く利用されることが期待される．
Sequence homology search is an approach for establishing structural and functional similarity with existing genes or proteins using a variety of databases containing a large number of DNA and protein sequences and the associated biological information. Sequence homology search is used in metagenomics. However, because of improvements in DNA sequencing technology, the volume of sequence data and the number of queries used in this analysis have been increasing rapidly in recent years, and the speed of sequence homology search has become insufficient. In this dissertation, we propose fast protein sequence homology search algorithms that can be applied to metagenomics using the latest DNA sequencing output. We used three approaches: development of novel protein sequence homology search algorithms, acceleration of protein sequence homology search with graphics processing unit (GPU), and parallelization of protein sequence homology search using modern supercomputing environments. We propose a novel protein sequence homology search algorithm that finds similarities between a query and database sequences based on the suffix arrays of these sequences. We used a subsequence search method relying on a similarity-based optimal length. This algorithm designated as GHOSTX provides approximately 165 times faster protein sequence homology search than BLASTX in the analysis of metagenomic data. In addition, we propose a novel protein sequence homology search method based on database subsequence clustering, designated as GHOSTZ. This method clusters similar subsequences retrieved from a database to reduce alignment candidates based on triangle inequality, and its performance in the analysis of metagenomic data is approximately two times faster than that of GHOSTX. In addition, we applied the GPUs and massively parallel computing systems, TSUBAME and the K computer, for protein sequence homology search and show that these approaches provide a significant acceleration of protein sequence homology search. DNA sequencing technology is constantly improving, resulting in generation of vast amounts of sequence data. This explosion of sequence volume makes computational analysis with contemporary tools more difficult. Here, we offer the algorithms, which may provide a potential solution to this problem.
identifier:oai:t2r2.star.titech.ac.jp:50265170
Format (IMT): application/pdf
Source: http://t2r2.star.titech.ac.jp/rrws/file/CTT100682805/ATD100000413/doctor_thesis_Shuji_Suzuki.pdf （fulltext）
http://t2r2.star.titech.ac.jp/rrws/file/CTT100682805/ATD100000413/doctor_thesis_Shuji_Suzuki.pdf
Access Restrictions: インターネット公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 東京工業大学 : 東京工業大学リサーチリポジトリ