21 papers · ranked by Valyu relevance
Étienne Grandjean, Louis Jachiet
| 1 | | Introduction and discussion of the RAM model | 2 | | --- | --- | --- | --- | | 2 | | Instruction sets for the RAM model | 6 | | | 2.1 | The RAM model with minimal instruction set | 6 | | | 2.2 | Two more instruction sets | 9 | | | 2.3 | Equivalence of our three instruction sets | 10 | | | 2.4 | Richer…
Sebastian Schmidt, Jarno N. Alanko
A fundamental operation in computational genomics is to reduce the input sequences to their constituent k-mers. For maximum performance of downstream applications it is important to store the k-mers in small space, while keeping the representation easy and efficient to use (i.e. without k-mer repetitions and in plain…
Nicola Rizzo, Manuel Cáceres, Veli Mäkinen
Background We study the problem of finding maximal exact matches (MEMs) between a query string Q and a labeled graph G. MEMs are an important class of seeds, often used in seed-chain-extend type of practical alignment methods because of their strong connections to classical metrics. A principled way to speed up…
Hongyu Zheng, Carl Kingsford, Guillaume Marçais
Minimizers are efficient methods to sample k-mers from genomic sequences that unconditionally preserve sufficiently long matches between sequences. Well-established methods to construct efficient minimizers focus on sampling fewer k-mers on a random sequence and use universal hitting sets (sets of k-mers that appear…
Jatin Batra, Naveen Garg, Amit Kumar
In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement pj , release date rj and weight wj . The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between…
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…
Ahsan Sanaullah, Nathaniel K. Brown, Pramesh Shakya, Arun Deegutla + 4 more
Lossless full text indexes are utilized in a myriad of applications in bioinformatics. The continuously decreasing cost of generating biological data has resulted in the need to build full text indexes on biological datasets of increasing size. Many compressed full text indexes have been developed to address this…
Tamar Pinhas, Shay Zakov, Dekel Tsur, Michal Ziv-Ukelson
We propose three algorithms for string edit distance with duplications and contractions. These include an efficient general algorithm and two improvements which apply under certain constraints on the cost function. The new algorithms solve a more general problem variant and obtain better time complexities with respect…
Ahsan Sanaullah, Degui Zhi, Shaojie Zhang
Durbin’s PBWT, a scalable data structure for haplotype matching, has been successfully applied to identical by descent (IBD) segment identification and genotype imputation. Once the PBWT of a haplotype panel is constructed, it supports efficient retrieval of all shared long segments among all individuals (long matches)…
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…
Mohammad Abdur Rob, Md. Zakir Hossen, Md. Kamal Hossen, Md. Mithun Ali + 2 more
Sorting algorithms play a crucial role in computing, but most are designed with rigid structure that are only efficient under certain conditions. Although some sorting algorithms perform well in some circumstances, they do not perform well on some resistant platforms. This study introduces Wall-L Merge Sort, which…
L. Kozma, Tan, Junqi
For many hard computational problems, simple algorithms that run in time 2 n · n O (1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this…
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O(m + n log n) time. This bound is known to be worst-case optimal via a reduction to sorting. Theoretical computer science has developed…
Ricardo Villanueva-Polanco
In this paper, we will study the key enumeration problem, which is connected to the key recovery problem posed in the cold boot attack setting. In this setting, an attacker with physical access to a computer may obtain noisy data of a cryptographic secret key of a cryptographic scheme from main memory via this data…
Chunchun Zhao, Sartaj Sahni
Background In the string correction problem, we are to transform one string into another using a set of prescribed edit operations. In string correction using the Damerau-Levenshtein (DL) distance, the permissible edit operations are: substitution, insertion, deletion and transposition. Several algorithms for string…
Qizheng He
The integer complexity f(n) of a positive integer n is a simple-looking problem in number theory with a long history. It is defined as the minimum number of 1's needed to represent n, using basic arithmetic expressions that only include 1, additions, multiplications and parentheses. For example, f(6) = 5, since 6 = (1…
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…
Shantanu Chhabra
We define an n-gon to be any convex polygon with n vertices. Let V represent the set of vertices of the polygon. A "proper" k-coloring refers to a function, f: V → {1, 2, 3, . . . k}, such that for any two vertices u and v, if f(u) = f(v), u is not adjacent to v. The purpose of this paper is to develop a recursive…
Nicolai Machholdt Høyer, Ove Christiansen
We present a new quasi-direct quantum molecular dynamics computational method which offer a compromise between quantum dynamics using a pre-computed potential energy surface (PES) and fully direct quantum dynamics. This method is termed the time-dependent adaptive density-guided approach (TD-ADGA) and is a method for…
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…
Authors not listed
Stochastic Simulation Algorithms (SSA) are a cornerstone in simulating Free Radical Polymerization (FRP) due to their accuracy and reliability. However, computational inefficiency remains a challenge for large-scale and complex polymerization systems. This work introduces a novel stochastic simulation algorithm…