权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

STUDY ON EFFICIENT SEARCH ALGORITHMS

高效搜索算法研究

基本信息

批准号：
06680326
负责人：
MIYANO Satoru
金额：
$ 1.41万
依托单位：
KYUSHU UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至 1995
项目状态：
已结题

项目摘要

Technologies for discoverring knowledge from nucleic acid and amino acid sequences are most expected in Genome Informatics/Molecular Bioinformatics. Various search techniques have traditionally playd a very important role in knowledge discovery from sequence. Our goal of this research are to establish the fundamental search strategies and to analyze its computational complexity. The following are the selection of the result for our study on efficient seach algorithms :We define a new framework for rewriting graphs, called a formal graph system (FGS) , which is a logic program having hypergraphs instead of terms in first-order logic. We show that the refutation tree problem for three subclasses of FGSs are computed efficiently in parallel.A partial walk in an undirected edge-colored graph G is a path in G.If a partial walk in G contains all edges of G,it is called a walk in G.The graph inference from walk is, given a string x, to find the smallest graph which can realize x as a walk in G.We prove that the graph inference from a walk for tree of bounded degree 3 is NP-complete.The knowledge on sequences is often expressed as a motif which is a pattern common to a family of sequences. We presents a greedy strategy for finding such motifs wich ambiguity just from positive and negative examples by exploiting the probabilistic argument.We have developed a parallel machine discovery system BONSAI Garden by employing these results. This system has succeeded in discovering resonable knowledge on a hodgepodge of amino acid sequences.

从核酸和氨基酸序列中提取知识的技术是基因组信息学/分子生物信息学中最受期待的技术。传统上，各种搜索技术在序列知识发现中扮演着非常重要的角色。我们的研究目标是建立基本的搜索策略，并分析其计算复杂度。以下是我们研究有效搜索算法的结果的选择：我们定义了一个新的重写图的框架，称为形式图系统（FGS），它是一个逻辑程序，具有超图而不是一阶逻辑中的术语。我们证明了FGS的三个子类的反驳树问题的并行计算是有效的.无向边着色图G中的部分行走是G中的一条路.如果G中的部分行走包含G的所有边，则称之为G中的行走.从行走的图推断是，给定一个字符串x，证明了由有界度为3的树的一个可走图的图推理是NP-关于序列的知识通常表示为基序，基序是序列家族共有的模式。我们提出了一种利用概率论从正反例中寻找这种模体的贪婪策略，并利用这些结果开发了一个并行机发现系统BONSAI Garden。这个系统已经成功地在大杂烩的氨基酸序列中发现了合理的知识。