检索结果-内蒙古大学图书馆

Refining Partial Invalidations for Indexed algebraic dynamic programming 3rd

3rd International Conference on Machine Learning, Optimization, and Data Science (MOD)

作者： Bacher, Christopher Raidl, Guenther R. TU Wien Algorithms & Complex Grp Vienna Austria

ISBN: (纸本)9783319729268;9783319729251

We consider dynamic programs modelled in a variant of the algebraic dynamic programming (ADP) framework which allows us to develop general purpose solvers for dynamic programming problems. In such dynamic programs the information accumulated in memoization tables is usually lost if the input data of the problem instance changes. We analyze those changes and how they affect the information stored for subproblems of a dynamic program. We then present the theory for a new algorithm for partial invalidation and incremental evaluation of ADPs based on a previous simpler algorithm. The new algorithm should reduce the amount of discarded information in dynamic programming tables and to speed up the reevaluation of dynamic programs in the face of changing inputs. In future work we will integrate the algorithms into a framework currently under development to conduct thorough experiments on their practical efficieny.

关键词： algebraic dynamic programming Formal grammars Incremental evaluation Logic programming

来源：评论

学校读者我要写书评

暂无评论

algebraic dynamic programming for multiple context-free grammars

引用

THEORETICAL COMPUTER SCIENCE 2016年 639卷 91-109页

作者： Riechert, Maik Siederdissen, Christian Hoener Zu Stadler, Peter F. Hsch Tech Wirtschaft & Kultur Leipzig Fak Informat Math & Nat Wissensch Gustav Freytag Str 42a D-04277 Leipzig Germany Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Fraunhofer Inst Zelitherapie & Immunol Perlickstr 1 D-04103 Leipzig Germany Univ Copenhagen Ctr Noncoding RNA Technol & Hlth Gronnegardsvej 3 DK-1870 Frederiksberg C Denmark Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

We present theoretical foundations, and a practical implementation, that makes the method of algebraic dynamic programming available for Multiple Context-Free Grammars. This allows to formulate optimization problems, where the search space can be described by such grammars, in a concise manner and solutions may be obtained efficiently. This improves on the previous state of the art which required complex code based on handwritten dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology. Appendix and supporting files available at: http://***/Software/gADP/ (C) 2016 Elsevier B.V. All rights reserved.

关键词： Multiple context-free grammars dynamic programming algebraic dynamic programming RNA secondary structure prediction Pseudoknots

来源：评论

学校读者我要写书评

暂无评论

Pareto optimization in algebraic dynamic programming

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2015年第1期10卷 1-20页

作者： Saule, Cedric Giegerich, Robert Univ Bielefeld Fac Technol D-33615 Bielefeld Germany Univ Bielefeld Ctr Biotechnol D-33615 Bielefeld Germany

Pareto optimization combines independent objectives by computing the Pareto front of its search space, defined as the set of all solutions for which no other candidate solution scores better under all objectives. This gives, in a precise sense, better information than an artificial amalgamation of different scores into a single objective, but is more costly to compute. Pareto optimization naturally occurs with genetic algorithms, albeit in a heuristic fashion. Non-heuristic Pareto optimization so far has been used only with a few applications in bioinformatics. We study exact Pareto optimization for two objectives in a dynamic programming framework. We define a binary Pareto product operator *(Par) on arbitrary scoring schemes. Independent of a particular algorithm, we prove that for two scoring schemes A and B used in dynamic programming, the scoring scheme A*B-Par correctly performs Pareto optimization over the same search space. We study different implementations of the Pareto operator with respect to their asymptotic and empirical efficiency. Without artificial amalgamation of objectives, and with no heuristics involved, Pareto optimization is faster than computing the same number of answers separately for each objective. For RNA structure prediction under the minimum free energy versus the maximum expected accuracy model, we show that the empirical size of the Pareto front remains within reasonable bounds. Pareto optimization lends itself to the comparative investigation of the behavior of two alternative scoring schemes for the same purpose. For the above scoring schemes, we observe that the Pareto front can be seen as a composition of a few macrostates, each consisting of several microstates that differ in the same limited way. We also study the relationship between abstract shape analysis and the Pareto front, and find that they extract information of a different nature from the folding space and can be meaningfully combined.

关键词： Pareto optimization dynamic programming algebraic dynamic programming RNA structure Sankoff algorithm

来源：评论

学校读者我要写书评

暂无评论

Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages

引用

ALGORITHMS 2024年第5期17卷 186页

作者： Delabre, Matteo El-Mabrouk, Nadia Univ Montreal Dept Informat & Rech Operat 2920 Chemin Tour Montreal PQ H3T 1J4 Canada

We present Synesth, the most comprehensive and flexible tool for tree reconciliation that allows for events on syntenies (i.e., on sets of multiple genes), including duplications, transfers, fissions, and transient events going through unsampled species. This model allows for building histories that explicate the inconsistencies between a synteny tree and its associated species tree. We examine the combinatorial properties of this extended reconciliation model and study various associated parsimony problems. First, the infinite set of explicatory histories is reduced to a finite but exponential set of Pareto-optimal histories (in terms of counts of each event type), then to a polynomial set of Pareto-optimal event count vectors, and this eventually ends with minimum event cost histories given an event cost function. An inductive characterization of the solution space using different algebras for each granularity leads to efficient dynamic programming algorithms, ultimately ending with an O(mn) time complexity algorithm for computing the cost of a minimum-cost history (m and n: number of nodes in the input synteny and species trees). This time complexity matches that of the fastest known algorithms for classical gene reconciliation with transfers. We show how Synesth can be applied to infer Pareto-optimal evolutionary scenarios for CRISPR-Cas systems in a set of bacterial genomes.

关键词： tree reconciliation algebraic dynamic programming multi-objective optimization horizontal gene transfer synteny fission unsampled lineages

来源：评论

学校读者我要写书评

暂无评论

Accuracy of RNA Structure Prediction Depends on the Pseudoknot Grammar 1

引用

15th Brazilian Symposium on Bioinformatics (BSB)

作者： Eggers, Dustyn zu Siederdissen, Christian Hoener Stadler, Peter F. Univ Leipzig Bioinformat Grp Dept Comp Sci Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Friedrich Schiller Univ Jena Fac Math & Comp Sci Theoret Bioinformat Lab Bioinformat High Throughput Anal Leutragraben 1 D-07743 Jena Germany Max Planck Inst Math Sci Leipzig Germany Univ Vienna Inst Theoret Chem Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst Santa Fe NM 87501 USA

ISBN: (数字)9783031211751

ISBN: (纸本)9783031211744;9783031211751

Most models for pseudoknotted RNA structures can be described by multi-context free grammars (MCFGs) and thus are amenable to dynamic programming algorithms. They differ strongly in their definition of admissible structures and thus the search space over which structures are optimized. The accuracy of structure prediction can be expected to depend on choice of the MCFG: models that are too inclusive likely over-predict pseudoknots, while restrictive models by their definition already exclude more complex pseudoknotted structures. A systematic analysis of the impact of the grammar, however, is difficult since available implementations use incomparable energy parameters. We show here that algebraic dynamic programming over MCFGs naturally disentangles energy models (as specified by the evaluation algebra) and the definition of search space defined by a MCFG. Preliminary computational experiments indicate that the choice of the grammar has an important impact already for short RNA sequences.

关键词： RNA Pseudoknots Multi-context free grammar algebraic dynamic programming ADPfusion

来源：评论

学校读者我要写书评

暂无评论

Adaptive structure metrics for automated feedback provision in intelligent tutoring systems

引用

NEUROCOMPUTING 2016年 192卷 3-13页

作者： Paassen, Benjamin Mokbel, Bassam Hammer, Barbara Univ Bielefeld Ctr Excellence Cognit Interact Technol CITEC Inspirat 1 D-33619 Bielefeld Germany

Typical intelligent tutoring systems rely on detailed domain-knowledge which is hard to obtain and difficult to encode. As a data-driven alternative to explicit domain-knowledge, one can present learners with feedback based on similar existing solutions from a set of stored examples. At the heart of such a data-driven approach is the notion of similarity. We present a general-purpose framework to construct structure metrics on sequential data and to adapt those metrics using machine learning techniques. We demonstrate that metric adaptation improves the classification of wrong versus correct learner attempts in a simulated data set from sports training, and the classification of the underlying learner strategy in a real Java programming dataset. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Metric learning Intelligent tutoring systems Sequential data Learning vector quantization algebraic dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Integrating Pareto Optimization into dynamic programming

引用

ALGORITHMS 2016年第1期9卷

作者： Gatter, Thomas Giegerich, Robert Saule, Cedric Univ Bielefeld Fac Technol D-33501 Bielefeld Germany Univ Bielefeld Ctr Biotechnol D-33501 Bielefeld Germany

Pareto optimization combines independent objectives by computing the Pareto front of the search space, yielding a set of optima where none scores better on all objectives than any other. Recently, it was shown that Pareto optimization seamlessly integrates with algebraic dynamic programming: when scoring schemes A and B can correctly evaluate the search space via dynamic programming, then so can Pareto optimization with respect to A and B. However, the integration of Pareto optimization into dynamic programming opens a wide range of algorithmic alternatives, which we study in substantial detail in this article, using real-world applications in biosequence analysis, a field where dynamic programming is ubiquitous. Our results are two-fold: (1) We introduce the operation of a Pareto algebra product in the dynamic programming framework of Bellman's GAP. Users of this framework can now ask for Pareto optimization with a single keystroke. Careful evaluation of the implementation alternatives by means of an extended Bellman's GAP compiler demonstrates the dependence of the best implementation choice on the application at hand. (2) We extract from our experiments several pieces of advice to programmers who do not use a system such as Bellman's GAP, but who choose to hand-craft their dynamic programming recurrences, incorporating Pareto optimization from scratch.

关键词： pareto optimization algebraic dynamic programming sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

引用

SCIENCE OF COMPUTER programming 2014年 87卷 2-22页

作者： Sauthoff, Georg Giegerich, Robert Univ Bielefeld Tech Fak D-33501 Bielefeld Germany Ctr Biotechnol D-33501 Bielefeld Germany

dynamic programming algorithms are traditionally expressed by a set of matrix recurrences-a low level of abstraction, which renders the design of novel dynamic programming algorithms difficult and makes debugging cumbersome. Bellman's GAP is a declarative, domain-specific language, which supports dynamic programming over sequence data. It implements the algebraic style of dynamic programming and allows one to specify algorithms by combining so-called yield grammars with evaluation algebras. Products on algebras allow to create novel types of analyses from already given ones, without modifying tested components. Bellman's GAP extends the previous concepts of algebraic dynamic programming in several respects, such as an "interleaved" product operation and the analysis of multi-track input. Extensive analysis of the yield grammar and the evaluation algebras is required for generating efficient imperative code from the algebraic specification. This article gives an overview of the analyses required and presents several of them in detail. Measurements with "real-world" applications demonstrate the quality of the code produced. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algebraic dynamic programming Domain-specific language Regular tree grammar Compiler optimization RNA structure prediction

来源：评论

学校读者我要写书评

暂无评论

Staged Parser Combinators for Efficient Data Processing

引用

ACM SIGPLAN NOTICES 2014年第10期49卷 637-653页

作者： Jonnalagedda, Manohar Coppey, Thierry Stucki, Sandro Rompf, Tiark Odersky, Martin EPFL LAMP Zurich Switzerland EPFL DATA Zurich Switzerland

Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to be interleaved with processing of parse results. Unfortunately, parser combinators are typically slow due to the high overhead of the host language abstraction mechanisms that enable composition. We present a technique for eliminating such overhead. We use staging, a form of runtime code generation, to dissociate input parsing from parser composition, and eliminate intermediate data structures and computations associated with parser composition at staging time. A key challenge is to maintain support for input dependent grammars, which have no clear stage distinction. Our approach applies to top-down recursive-descent parsers as well as bottom-up nondeterministic parsers with key applications in dynamic programming on sequences, where we auto-generate code for parallel hardware. We achieve performance comparable to specialized, hand-written parsers.

关键词： Parser combinators multi-stage programming algebraic dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Staged Parser Combinators for Efficient Data Processing 14

Staged Parser Combinators for Efficient Data Processing

引用

2014 ACM International Conference on Object-Oriented-programming-Systems-Languages-and-Applications (OOPSLA 14)

作者： Jonnalagedda, Manohar Coppey, Thierry Stucki, Sandro Rompf, Tiark Odersky, Martin EPFL LAMP Zurich Switzerland EPFL DATA Zurich Switzerland

ISBN: (纸本)9781450325851

关键词： Parser combinators multi-stage programming algebraic dynamic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：