塩基配列用の高速パタ-ン照合アルゴリズムの研究

碱基序列高速模式匹配算法研究

• 批准号: 03266212
• 负责人: 篠原 武
• 金额: $ 1.92万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-03266212/
• 关键词: 文字列パタ-ン照合; DNA; 塩基配列デ-タベ-ス; ゲノム解析; デ-タ圧縮; 情報検索; Huffman符号; 高速化

文字列パタ-ン照合とは,文字列パタ-ンのテキスト中における出現位置を検出することであり,これまでにも情報検索システムやデ-タベ-スシステムにおいて最も基本的かつ重要な機構として活用されてきている.遺伝情報の本体であるDNAは,基本的には,‘A',‘T','C',‘G'の4種類の記号からなる文字列である.本研究の目的は,パタ-ン照合の処理対象がDNAの塩基配列である場合を取り上げて,その高速なアルゴリズムの実現方法について研究を進めていくとともに,実際にゲノム研究者のツ-ルとして有用なシステムの構築を行うことである.本年度は,次の2点を中心に研究を進めた。1.塩基配列用パタ-ン照合アルゴリズムの高速化さまざまな観点から塩基配列用のパタ-ン照合アルゴリズムについて考察し,その高速化の可能性を探る.とくに,情報圧縮を利用する高速化や並列化による高速化について塩基配列への適用可能性を検討する。DNA塩基配列デ-タを構成する文字種は非常に少なく,しかもそのほとんどが,‘A',‘T',‘C',‘G'であるが,通常のシステムでは,これをそのまま計算機の文字(8ビット)で表現している.このデ-タをHuffman符号によって圧縮し,それをそのまま復号することなく走査するアルゴリズムを考案した.これにより,デ-タを効率的に圧縮し,しかも検索を高速に実行することが可能であることがわかった.2.テキストデ-タベ-ス管理システムSIGMAの整備SIGMAは,著者らが開発し,九州大学大型計算機センタ-で一般に公開している汎用のテキストデ-タベ-ス管理システムであり,高速な文字列パタ-ン照合アルゴリズムを駆使した効果的な情報システムである。このSIGMAシステムをゲノム研究者のツ-ルとして活用できるように整備していく。DNA塩基配列デ-タベ-スGanBankをSIGMAのファイルに変換し,管理・検索できることを確認した。これを,全国の研究者が共同利用できるデ-タベ-スとして公開すれば,ゲノム研究者によるさまざまな検索が可能になる.

The text column is composed of two parts: the text column is composed of two DNA, basic,'A',' T','C',' G', four kinds of symbols. The purpose of this study is to improve the efficiency of DNA gene alignment and to develop high speed DNA gene expression methods. This year, the second time, the center of research. 1. To investigate the possibility of speeding up the system for base alignment and to explore the possibility of speeding up the system for base alignment. In this paper, the possibility of application of high speed and parallel information compression is discussed. DNA base sequence is composed of a very small number of text species, such as 'A',' T','C',' G', which are usually represented by computer text (8). The Huffman symbol is compressed, and the number of times it is compressed is increased. 2. The main purpose of this project is to develop a general public mainframe computer system at Kyushu University, which is widely used in the field of computer science and technology. High speed text columns are used to capture information from a variety of sources The SIGMA system requires researchers to prepare for the future. DNA sequencing- This is why researchers across the country can make common use of the information available to the public, and it is important for researchers to find out what is possible.

项目成果

深町 修一,篠原 武: "圧縮デ-タのための高速文字列パタ-ン照合技法" 情報処理学会全国大会(第43回)論文集. vol.4. 83-84 (1991)

Shuichi Fukamachi、Takeshi Shinohara：“压缩数据的高速字符串模式匹配技术”第 43 届日本信息处理学会全国会议论文集第 83-84 卷（1991 年）。

Arikawa,S.,Miyano,S.,Kuhara,S.,Shinohara,A.,Shinohara,T.: "A learning algorithm for elementary formal systems and its experiments on identication of transmembrane domains" Proceedings of the 25th Hawaii International Conference on System Sciences. vol.I.

Arikawa,S.,Miyano,S.,Kuhara,S.,Shinohara,A.,Shinohara,T.：“基本形式系统的学习算法及其跨膜域识别实验”第 25 届夏威夷国际会议论文集

有川 節夫,久原 哲,宮野 悟 篠原 歩,篠原 武: "ネガティブモチ-フの機械発見" 第2回公開ワ-クショップ「ヒトゲノム計画と情報解析技術」. 62-65 (1991)

Setsuo Arikawa、Tetsu Kuhara、Satoru Miyano、Ayumu Shinohara、Takeshi Shinohara：“负基序的机械发现”第二届公共研讨会“人类基因组计划和信息分析技术”62-65（1991）。

篠原 武,有川 節夫,久原 哲,宮原 哲浩,井上 仁,篠原 歩,内田 智之: "テキストデ-タベ-ス管理システムSIGMAとゲノム解析への応用" 第2回公開ワ-クショップ「ヒトゲノム計画と情報解析技術」. 29-32 (1991)

Takeshi Shinohara、Setsuo Arikawa、Tetsu Kuhara、Tetsuhiro Miyahara、Hitoshi Inoue、Ayumu Shinohara、Tomoyuki Uchida：“文本数据库管理系统 SIGMA 及其在基因组分析中的应用”第二届公开研讨会“人类基因组计划与信息分析技术”。29-32 (1991)

深町 修一,篠原 武,竹田 正幸: "可変長符号圧縮デ-タのための文字列パタ-ン照合ーゲノム情報の高速検索技法ー" 「1992年情報学」シンポジウム. 95-103 (1992)

Shuichi Fukamachi、Takeshi Shinohara、Masayuki Takeda：“可变长度代码压缩数据的字符串模式匹配 - 基因组信息的高速检索技术”1992 年信息学研讨会 95-103（1992）。