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

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

• 批准号: 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/)。

今年，我们尝试将模式搜索的目标模式类从去年主要使用的简单子字符串类扩展到允许赋值、删除和插入的近似字符串模式。具体来说，我们新考虑了一类称为 VLDC（可变长度无关）模式的模式，其中包含可以匹配任意字符串的“通配符”，并使 VLDC 模式的查询速度更快。我们开发了一种称为 MASDAWG 的字符串索引结构。可以进行处理。此外，我们还研究和开发了一种使用该索引结构有效搜索 VLDC 模式的算法。通过以这种方式提高描述模式的能力，期望在搜索模式时可以获得更多有用的知识。为了验证这一点，当给定一组正例和反例的字符串作为数据时，我们开发了一种算法，用于搜索最具体地只出现在正例中或仅出现在反例中的VLDC模式，并实现它。应用于数据。当我们将开发的算法应用于去年分析的具有 N 端细胞内定位信号的氨基酸序列数据时，我们发现分类精度提高了，并且发现的模式更好地匹配了定位信号的已知特征。它被捕获了。此外，我们分析了基因DNA序列中的长内含子序列，并成功发现了长内含子特征的VLDC模式。该程序使用名为 Objective Caml 的函数式语言开发，部分源代码在 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。