文字の分類とパターン探索アルゴリズムの研究

字符分类与模式搜索算法研究

• 批准号: 13780271
• 负责人: 坂内 英夫
• 金额: $ 1.34万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780271/
• 关键词: alphabet indexing; amino acid index; pattern discovery; knowledge discovery; BONSAI; string matching; 知識発見; iPSORT

本年度はパターン探索の対象となるパターンのクラスを、昨年度まで主に用いていた単純な部分文字列クラスや、代入・削除・挿入を許した近似文字列パターンから拡張を試みた。具体的には任意の文字列とマッチする事が可能な「ワイルドカード文字」を含むVLDC (variable length don't care) パターンと呼ばれるパターンのクラスについて新たに考察し、VLDCパターンの問合せを高速に処理する事が可能なMASDAWGと呼ばれる文字列の索引構造を開発した。更にこの索引構造を用いて効率的にVLDCパターンの探索を行なうアルゴリズムに関して研究・開発を行なった。このようにパターンの記述力を高める事で、パターン探索に際してより有用な知識を得られる事が期待される。これを検証するために、データとして正例と負例の文字列集合が与えられた時に、正例のみ、もしくは負例のみに、最も特異的に現われるVLDCパターンを探索するアルゴリズムを開発し、実データに対して適用した。開発したアルゴリズムを昨年度に解析したN-末端細胞内局在化シグナルを持つアミノ酸配列データに対して適用したところ、分類精度の向上と、発見されたパターンが局在化シグナルに関して既知の特徴を良く捉えている事が確認できた。他には遺伝子のDNA配列における長大なイントロンの配列の解析を行ない、長いイントロンに特徴的なVLDCパターンを発見する事に成功した。プログラムの開発はObjective Camlと呼ばれる関数型言語で行ない、ソースコードは一部GPLで公開している(http://biocaml.org/)。

This year, we will explore the target text, and last year, we will use the target text to select the target text, substitute the target text, and delete the target text. The specific text string is possible to include VLDC (variable length don't care), and VLDC (variable length don't care). In addition, the index structure is used to explore the VLDC network. The power of description is high, the knowledge is useful, and the expectation is high. The text string set of the positive and negative examples is open to exploration and application. The N-terminal intracellular localization was analyzed and the acid alignment was determined. The classification accuracy was improved. The characteristics of the N-terminal intracellular localization were confirmed. He succeeded in identifying the DNA sequence of the DNA sequence and in identifying the VLDC sequence. The development of the platform will be implemented in Objective Caml and Call for Numbers, and the software will be made public in a GPL (http://biocaml.org/).

项目成果

H.Bannai, et al.: "Concepts for Accelerating the Computational Knowledge Discovery Process"Linkoping Electronic Articles in Computer and Information Science. 6. (2001)

H.Bannai 等人：“加速计算知识发现过程的概念”林雪平计算机和信息科学电子文章。

S.Ott et al.: "Intrasplicing-Analysis of Long Intron Sequences"Proc. Pacific Symposium on Biocomputing. 8. 339-350 (2003)

S.Ott 等人：“长内含子序列的内剪接分析”Proc。