24 papers · ranked by Valyu relevance
Chao Pan, Zhicheng Lv, Xia Hua, Hongyan Li
Normalized cross-correlation is an important mathematical tool in digital signal processing. This paper presents a new algorithm and its systolic structure for digital normalized cross-correlation, based on the statistical characteristic of inner-product. We first introduce a relationship between the inner-product in…
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in…
Jie Huang, Tian Zhou, Weidong Du, Jiajun Shen + 1 more
A new fast deconvolved beamforming algorithm is proposed in this paper, and it can greatly reduce the computation complexity of the original Richardson-Lucy (R-L algorithm) deconvolution algorithm by utilizing the convolution theorem and the fast Fourier transform technique. This algorithm makes it possible for…
Max Doblas, Oscar Lostes-Cazorla, Quim Aguado-Puig, Cristian Iñiguez + 2 more
Pairwise sequence alignment is a core component of multiple sequencing-data analysis tools. Recent advancements in sequencing technologies have enabled the generation of longer sequences at a much lower price. Thus, long-read sequencing technologies have become increasingly popular in sequencing-based studies. However…
Cunzhe Lu, Xiaogang Qi, Kai Ding, Baoguo Yu + 1 more
In complex environments such as those with low textures or obvious brightness changes, point features extracted from a traditional FAST algorithm cannot perform well in pose estimation. Simultaneously, the number of point features extracted from FAST is too large, which increases the complexity of the build map. To…
Sariel Har-Peled
We are given a directed graph G = (V, E) with n vertices and m edges, with positive weights on the edges, and a parameter k > 0. We show how to compute, for every vertex v ∈ V , its k nearest-neighbors. The algorithm runs in O(k(n log n + m)) time, and follows by a somewhat careful modification of Dijkstra's shortest…
Shay Mozes, Yahav Nussbaum, Oren Weimann
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense…
Ali Dasdan
The Fibonacci numbers are a sequence of integers in which every number after the first two, 0 and 1, is the sum of the two preceding numbers. These numbers are well known and algorithms to compute them are so easy that they are often used in introductory algorithms courses. In this paper, we present twelve of these…
Chao Chen, Bruno da Silva, Ruiqi Chen, Shun Li + 3 more
'Chengyu Liu' 'Fernando Morgado-Dias'] Entropy is one of the most fundamental notions for understanding complexity. Among all the methods to calculate the entropy, sample entropy (SampEn) is a practical and common method to estimate time-series complexity. Unfortunately, SampEn is a time-consuming method growing in…
Michal Koucký, Michael Saks
For any T ≥ 1, there are constants R = R(T ) ≥ 1 and ζ = ζ(T ) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n 1+ 1 T ) and outputs an upper bound U on the edit distance of dedit(x, y) that with high probability, satisfies U ≤ R(dedit(x, y)…
Ragnar Groot Koerkamp, Igor Martayan
Because of the rapidly-growing amount of sequencing data, computing sketches of large textual datasets has become an essential preprocessing task. These sketches are typically much smaller than the input sequences, but preserve sufficient information for downstream analysis. Minimizers are an especially popular…
Gene Myers, Richard Durbin, Chenxi Zhou
FastGA finds alignments between two genome sequences more than an order of magnitude faster than previous methods that have comparable sensitivity. Its speed is due to (a) a carefully engineered architecture involving only cache-coherent MSD radix sorts and merges, (b) a novel algorithm for finding adaptive seed hits…
Fabio Cannizzo
Given an array X of N + 1 strictly ordered floating point numbers1 and a floating point number z belonging to the interval [X0, XN), a common problem in numerical methods is to find the index i of the interval [Xi , Xi+1) containing z, i.e. the index of the largest number in the array X which is smaller or equal than…
Sebastian Wild, Markus E. Nebel, Ralph Neininger
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of…
Lionel Zoubritzky, François-Xavier Coudert
We present here an open-source Julia library for the topological identification of crystalline materials, with algorithmic and computational improvements over the previously available software in the field, resulting in a speed increase of one order of magnitude. This new algorithm and implementation can therefore be…
Ragnar Groot Koerkamp, Pesho Ivanov
Sequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time (25). We solve exact global pairwise alignment with respect to edit distance by using the A shortest…
Jordan M. Eizenga, Benedict Paten
Modern genomic sequencing data is trending toward longer sequences with higher accuracy. Many analyses using these data will center on alignments, but classical exact alignment algorithms are infeasible for long sequences. The recently proposed WFA algorithm demonstrated how to perform exact alignment for long, similar…
Bastian Wiederhold, Martin Stemmler, Andreas V.M. Herz
While our senses transmit information at rates exceeding 10^6^ bit/s, high-level cognitive processing is thought to be much slower, on the order of 10 bit/s regardless of the task^1^. It is unclear, though, whether this limit holds when the human mind is challenged. To test how fast one can process abstract…
Yann Garniron, Thomas Applencourt, Kevin Gasperich, Anouar Benali + 15 more
Quantum Package is an open-source programming environment for quantum chemistry specially designed for wave function methods. Its main goal is the development of determinant-driven selected configuration interaction (sCI) methods and multi-reference second-order perturbation theory (PT2). The determinant-driven…
Authors not listed
Atomistic simulations provide essential mechanistic insights into chemical processes, yet many important phenomena in chemistry and materials science occur on timescales that are inaccessible to molecular dynamics. Existing computational approaches force a choice between atomic resolution on relatively short timescales…
Authors not listed
Computing electrostatic interactions remains the bottleneck of molecular dynamics (MD) simulations despite more than a century of effort in developing methods to accelerate the calculation. Previously we have developed the Spherical Grid and Treecode (SGT) and Gauss-Legendre-Spherical-t (GLST) algorithms for…
Justin Eilertsen, Wylie Stroberg, Santiago Schnell
The determination of a substrate or enzyme activity by coupling of one enzymatic reaction with another easily detectable (indicator) reaction is a common practice in the biochemical sciences. Usually, the kinetics of enzyme reactions is simplified with singular perturbation analysis to derive rate or time course…
Justin Eilertsen, Wylie Stroberg, Santiago Schnell
The determination of a substrate or enzyme activity by coupling of one enzymatic reaction with another easily detectable (indicator) reaction is a common practice in the biochemical sciences. Usually, the kinetics of enzyme reactions is simplified with singular perturbation analysis to derive rate or time course…
Justin Eilertsen, Santiago Schnell
As a case study, we consider a coupled enzyme assay of sequential enzyme reactions obeying the Michaelis--Menten reaction mechanism. The sequential reaction consists of a single-substrate, single-enzyme non-observable reaction followed by another single-substrate, single-enzyme observable reaction (indicator reaction).…