25 papers · ranked by Valyu relevance
Thomas J. Sargent, John Stachurski
| Preface | | | viii | | --- | --- | --- | --- | | Common Symbols | | | xi | | | Common Abbreviations | | xii | | 1 | Introduction | | 1 | | | 1.1 Bellman Equations | | 3 | | | 1.1.1 | Finite-Horizon Job Search | 3 | | | 1.1.2 Infinite Horizon | | 10 | | | 1.2 Stability and Contractions | | 12 | | | 1.2.1 Vector Space…
Peter Steffen, Robert Giegerich
Background Dynamic programming is a widely used programming technique in bioinformatics. In sharp contrast to the simplicity of textbook examples, implementing a dynamic programming algorithm for a novel and non-trivial application is a tedious and error prone task. The algebraic dynamic programming approach seeks to…
David H. Lee, Aditya Prasad, Ramiro Deo-Campo Vuong, Tianyu Wang + 2 more
'Eric Han' 'David Kempe'] Dynamic programming (DP) is a fundamental and powerful algorithmic paradigm taught in most undergraduate (and many graduate) algorithms classes. DP problems are challenging for many computer science students because they require identifying unique problem structures and a refined understanding…
Ryo Kuroiwa, J. Christopher Beck
For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the 'holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm…
Mateusz Gruzewski, Marek Palkowski, Ramon Antonio Rodriges Zalipynis
In this article, we present an efficient and concise OpenMP implementation of the Nussinov RNA folding algorithm, a well-known representative of non-serial polyadic dynamic programming (NPDP). Our goal is to develop an optimized implementation that can serve as a template for related dynamic programming applications.…
Ryo Kuroiwa, J. Christopher Beck
- We propose domain-independent dynamic programming (DIDP), a novel model-based paradigm for combinatorial optimization. - The modeling language for DIDP is designed so that a user can investigate efficient models by incorporating redundant information. - We implement DIDP solvers using heuristic search in an…
Kathrin Ungru, Xiaoyi Jiang
Many applications in biomedical imaging have a demand on automatic detection of lines, contours, or boundaries of bones, organs, vessels, and cells. Aim is to support expert decisions in interactive applications or to include it as part of a processing pipeline for automatic image analysis. Biomedical images often…
Christian Höner zu Siederdissen, Sonja J Prohaska, Peter F Stadler
Background Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform…
Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases…
Maren Brand, Nguyen Khoa Tran, Philipp Spohr, Sven Schrinner + 1 more
We consider the homo-edit distance problem, which is the minimum number of homo-deletions or homo-insertions to convert one string into another. A homo-insertion is the insertion of a string of equal characters into another string, while a homo-deletion is the inverse operation. We show how to compute the homo-edit…
Anurag Dutta, K. Lakshmanan, John Harshith, Aditya Ramamoorthy
Problem: The Maximal Stretch Authors: ['Anurag Dutta' 'K. Lakshmanan' 'John Harshith' 'Aditya Ramamoorthy'] Abstract. Mathematical Selection is a method in which we select a particular choice from a set of such. It have always been an interesting field of study for mathematicians. Combinatorial optimisation is the…
Ken D Nguyen, Yi Pan, Ge Nong
Background One of the most fundamental and challenging tasks in bio-informatics is to identify related sequences and their hidden biological significance. The most popular and proven best practice method to accomplish this task is aligning multiple sequences together. However, multiple sequence alignment is a computing…
Eugene Callahan, Robert A. Murphy, Anas Elghafari
Students of Computer Science often wonder when, exactly, one can apply a greedy algorithm to a problem, and when one must use the more complicated and time-consuming techniques of dynamic programming. This paper argues that the existing pedagogical literature does not offer clear guidance on this issue. We suggest…
Nikolai Baudis, Pierre Barbera, Sebastian Graf, Sarah Lutteropp + 3 more
In the context of a master level programming practical at the computer science department of the Karlsruhe Institute of Technology, we developed and make available two independent and highly optimized open-source implementations for the pair-wise statistical alignment model, also known as TKF91, that was developed by…
Arseny Shur, Ido Tziony, Yaron Orenstein
Minimizers are sampling schemes which are ubiquitous in almost any high-throughput sequencing analysis. Assuming a fixed alphabet of size σ, a minimizer is defined by two positive integers k, w and a linear order ρ on k-mers. A sequence is processed by a sliding window algorithm that chooses in each window of length w…
Yelena Frid, Dan Gusfield
Background The problem of computationally predicting the secondary structure (or folding) of RNA molecules was first introduced more than thirty years ago and yet continues to be an area of active research and development. The basic RNA-folding problem of finding a maximum cardinality, non-crossing, matching of…
Lorién López-Villellas, Cristian Iñiguez, Albert Jiménez-Blanco, Quim Aguado-Puig + 4 more
Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce…
Authors not listed
Deriving versatile and robust mechanistic models from experimental data is a key challenge in engineering and natural sciences. This is especially true in chemical reaction engineering, where reactor manufacturers and operators increasingly pursue the development and maintenance of digital twins that rely on frequent…
Mikko Rautiainen, Veli Mäkinen, Tobias Marschall
Graphs are commonly used to represent sets of sequences. Either edges or nodes can be labeled by sequences, so that each path in the graph spells a concatenated sequence. Examples include graphs to represent genome assemblies, such as string graphs and de Bruijn graphs, and graphs to represent a pan-genome and hence…
Enrico Seiler, Myrthe Willemsen, Vitor C. Piro, Knut Reinert
A continued decrease in sequencing costs has facilitated the exponential increase in available sequencing data, with public databases like the European Nucleotide Archive (ENA) and Sequence Read Archive (SRA) reaching well in the order of petabases [1, 2]. This has been the incentive to develop more scalable tools for…
Elena Zamaraeva, Christopher M. Collins, Dmytro Antypov, Vladimir V. Gusev + 6 more
Crystal Structure Prediction (CSP) is a fundamental computational problem in materials science. Basin-hopping is a prominent CSP method that combines global Monte Carlo sampling to search over candidate trial structures with local energy minimisation of these candidates. The sampling uses a stochastic policy to…
Ragnar Groot Koerkamp
We introduce APA2, an exact global pairwise aligner with respect to edit distance. The goal of APA2 is to unify the near-linear runtime of APA on similar sequences with the efficiency of dynamic programming (DP) based methods. Like Edlib, APA2 uses Ukkonen’s band doubling in combination with Myers’ bitpacking. APA2 1)…
Authors not listed
Automated chemistry platforms hold the potential to enable large-scale organic synthesis campaigns, such as producing a library of compounds for biological evaluation. The efficiency of such platforms will depend on the schedule according to which the synthesis operations are executed. In this work, we study the…
Michele Stasi, Alba Monferrer i Sureda, Leon Babl, Sreekar Wunnava + 5 more
Molecular machines, such as ATPases or motor proteins, couple the catalysis of a chemical reaction, most commonly hydrolysis of nucleotide triphosphates, to their conformational change. In essence, they continuously convert a chemical fuel to drive their motion. An outstanding goal of nanotechnology remains to…
Liwei Cao, Danilo Russo, Vassilios S. Vassiliadis, Alexei Lapkin
A mixed-integer nonlinear programming (MINLP) formulation for symbolic regression was proposed to identify physical models from noisy experimental data. The formulation was tested using numerical models and was found to be more efficient than the previous literature example with respect to the number of predictor…