著者

鈴木 脩司 石田 貴士 秋山 泰

出版者

情報処理学会

雑誌

研究報告バイオ情報学(BIO) (ISSN:18840930)

巻号頁・発行日

vol.2010, no.20, pp.1-6, 2010-12-09

---

近年,DNA 配列等の配列決定技術の向上により高速に配列データを得ることが可能となった.これにより DNA 配列及びタンパク質配列のデータベースのデータ量が爆発的に増加している.このため大量の配列データに対して巨大な DB への相同性検索を行う機会が多くなってきてる.しかし,大規模なデータを用いた相同性検索では,BLAST など従来のツールでは解析が間に合わないという問題がある.本研究では Suffix Array を用いてクエリのインデックスを,FM-index を用いて DB のインデックスを構築し,これらのインデックスを用いてミスマッチをある程度許して短い領域で高いスコアとなる部分を見つけ,その部分の周辺をアラインメントするアルゴリズムを提案した.その結果,従来用いられてきた BLAST 以上の精度を保ったまま,約 10 倍の高速化を達成した.In recent years, a lot of biological sequence data can be determined easily and the size of DNA/protein sequence databases is increasing explosively because of the improvement of sequencing technologies. However, such a huge sequence data causes a problem that even general homology search analyses by using BLAST become difficult in terms of the computation cost. Therefore, we designed a new homology search algorithm that finds alignment candidates based on the suffix array of queries and the FM-index of a database. As results, the proposed method achieved about 10-fold speed up than BLAST.

著者

鈴木 脩司 石田 貴士 秋山 泰

雑誌

研究報告バイオ情報学(BIO)

巻号頁・発行日

vol.2012, no.24, pp.1-7, 2012-06-21

---

我々は以前に suffix array を用いた高速な相同性検索システムを提案したが,近年の次世代シークエンサーの進歩が目覚ましく,得られる配列データは増加しており,さらなる高速化が必要とされている.このため,本研究では従来システムの改良を試み,長さ L hash のすべての文字列の suffix array の検索結果を予め計算しておき,これを保存しておく.そして,検索の際は L hash 文字目までの検索には保存しておいたものを読み出すことで高速化した.また,このシステムを用いてエピゲノム解析へも対応するために,バイサルファイト処理を行った DNA 断片配列のマッピングができるように改良を行った.We developed the system for fast homology search using suffix array. However, next generation sequencers are improving gradually and become to produce larger data than previous sequencers. Thus, we have developed a new faster system. To accelerate search using suffix array, we store the results of searching patterns whose length is less than Lhash and use them as caches. In addition, we enhanced our system to map bisulfite reads for epigenomics.

著者

鈴木 脩司 石田 貴士 秋山 泰

出版者

情報処理学会

雑誌

研究報告数理モデル化と問題解決(MPS) (ISSN:18840930)

巻号頁・発行日

vol.2010, no.20, pp.1-6, 2010-12-09

被引用文献数

1

---

近年,DNA 配列等の配列決定技術の向上により高速に配列データを得ることが可能となった.これにより DNA 配列及びタンパク質配列のデータベースのデータ量が爆発的に増加している.このため大量の配列データに対して巨大な DB への相同性検索を行う機会が多くなってきてる.しかし,大規模なデータを用いた相同性検索では,BLAST など従来のツールでは解析が間に合わないという問題がある.本研究では Suffix Array を用いてクエリのインデックスを,FM-index を用いて DB のインデックスを構築し,これらのインデックスを用いてミスマッチをある程度許して短い領域で高いスコアとなる部分を見つけ,その部分の周辺をアラインメントするアルゴリズムを提案した.その結果,従来用いられてきた BLAST 以上の精度を保ったまま,約 10 倍の高速化を達成した.In recent years, a lot of biological sequence data can be determined easily and the size of DNA/protein sequence databases is increasing explosively because of the improvement of sequencing technologies. However, such a huge sequence data causes a problem that even general homology search analyses by using BLAST become difficult in terms of the computation cost. Therefore, we designed a new homology search algorithm that finds alignment candidates based on the suffix array of queries and the FM-index of a database. As results, the proposed method achieved about 10-fold speed up than BLAST.

著者

鈴木 脩司 石田 貴士 秋山 泰

雑誌

研究報告バイオ情報学(BIO)

巻号頁・発行日

vol.2013-BIO-34, no.14, pp.1-7, 2013-06-20

---

メタゲノム解析では DNA 配列をアミノ酸配列に変換して相同性検索を行うが、次世代シークエンサの登場によって得られるようになった大量の DNA 断片配列の処理に多くの時間がかかるようになっている。このため、我々はあらかじめデータベースを部分文字列に分割して、類似度が高い部分文字列をまとめておき、まずその代表点に対して検索を行うことで効率よく検索する手法を開発した。