课题基金 / 基金详情

STUDY ON EFFICIENT SEARCH ALGORITHMS

STUDY ON EFFICIENT SEARCH ALGORITHMS
高效搜索算法研究
批准号:
06680326
负责人:
MIYANO Satoru
金额:
$1.41万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for General Scientific Research (C)
财政年份:
1994
资助国家:
日本
项目状态:
已结题
起止时间:
1994 至 1995

项目摘要

项目成果

MIYANO Satoru的其他基金

相似基金

相关文献

中文摘要
翻译
从核酸和氨基酸序列中发现知识的技术在基因组信息学/分子生物信息学中是最受期待的。传统上,各种搜索技术在从序列中发现知识方面起着非常重要的作用。我们的研究目标是建立基本的搜索策略,并分析其计算复杂度。我们定义了一个用于重写图的新框架,称为形式图系统(FGS),它是一个具有超图而不是一阶逻辑项的逻辑程序。我们证明了对fgs的三个子类的反驳树问题的并行有效计算。无向边彩色图G中的部分游动是G中的一条路径,如果G中的部分游动包含G的所有边,则称为G中的游动。游动的图推理是,给定一个字符串x,找出能实现x在G中游动的最小图,证明了对有界3度树的游动的图推理是np完全的。关于序列的知识通常用基序来表示,基序是一组序列所共有的模式。我们提出了一种贪心策略,利用概率论证从正反两个例子中寻找模棱两可的母题。我们利用这些结果开发了一个平行机器发现系统BONSAI Garden。这个系统已经成功地在氨基酸序列的大杂烩上发现了合理的知识。
英文摘要
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.
期刊论文(47)
专著(0)
科研奖励(0)
会议论文
Tomoyuki Uchida: "Parallel algorithms for refutation tree problem on formal graph systems" IEICE Transactions on Information and Systems. E78-D. 99-112 (1995)
Tomoyuki Uchida:“形式图系统上反驳树问题的并行算法”IEICE Transactions on Information and Systems。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
Shinichi Shimozono: "An approximation algorithm for alphabet indexing problem" Algorithms and Computation, 6th International Symposium,ISAAC'95 (Lecture Notes in Computer Science). 1004. 2-11 (1995)
Shinichi Shimozono:“字母表索引问题的近似算法”算法与计算,第六届国际研讨会,ISAAC95(计算机科学讲义)。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
S.Shimozono and S.Miyano: "Complexity of Finding Alphabet Indexing" IEICE Trans.Inf.and Syst.E78-D. 13-18 (1995)
S.Shimozono 和 S.Miyano:“查找字母索引的复杂性”IEICE Trans.Inf. 和 Syst.E78-D。
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
Erika Tateishi: "A greedy strategy for finding motifs from yes-no examples" Pacific Symposium on BIOCOMPUTING 96. 599-613 (1996)
Erika Tateishi:“从是非例子中寻找主题的贪婪策略”太平洋生物计算研讨会 96. 599-613 (1996)
DOI: --
发表时间:
期刊:
影响因子: --
作者: []
通讯作者:
共 21 条
    Drug-response pathway analysis methods based on network analysis
    • 批准号:
      22300099
    • 项目类别:
      Grant-in-Aid for Scientific Research (B)
    • 资助金额:
      $5.57万
    • 财政年份:
      2010
    • 负责人:
      MIYANO Satoru
    • 依托单位:
    In Silico Search for Drug Target Pathways by Gene Networks
    • 批准号:
      18300097
    • 项目类别:
      Grant-in-Aid for Scientific Research (B)
    • 资助金额:
      $11.33万
    • 财政年份:
      2006
    • 负责人:
      MIYANO Satoru
    • 依托单位:
    Estimation and simulation of gene networks for developing in silico biological networks
    • 批准号:
      17017008
    • 项目类别:
      Grant-in-Aid for Scientific Research on Priority Areas
    • 资助金额:
      $59.84万
    • 财政年份:
      2005
    • 负责人:
      MIYANO Satoru
    • 依托单位:
    Information Scientific Foundations of Knowledge Discovery from Proteome Data
    • 批准号:
      15300099
    • 项目类别:
      Grant-in-Aid for Scientific Research (B)
    • 资助金额:
      $10.56万
    • 财政年份:
      2003
    • 负责人:
      MIYANO Satoru
    • 依托单位:
    海外基金