30 citations · 76 across the 8 of their papers we have counts for
11 papers
Theoretical analysis of edit distance algorithms: an applied perspective
Paul Medvedev
Given its status as a classic problem and its importance to both theoreticians and practitioners, edit distance provides an excellent lens through which to understand how the theor…
Data structures to represent a set of k-long DNA sequences
Rayan Chikhi, Jan Holub, Paul Medvedev
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of…
Bipartite Graphs of Small Readability
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch +4
We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bio…
Modeling Biological Problems in Computer Science: A Case Study in Genome Assembly
Paul Medvedev
As computer scientists working in bioinformatics/computational biology, we often face the challenge of coming up with an algorithm to answer a biological question. This occurs in m…
TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes
Ilia Minkin, Son Pham, Paul Medvedev
Motivation: De Bruijn graphs have been proposed as a data structure to facilitate the analysis of related whole genome sequences, in both a population and comparative genomic setti…
Safe and complete contig assembly via omnitigs
Alexandru I. Tomescu, Paul Medvedev
Contig assembly is the first stage that most assemblers solve when reconstructing a genome from a set of reads. Its output consists of contigs -- a set of strings that are promised…
On the readability of overlap digraphs
Rayan Chikhi, Paul Medvedev, Martin Milanic +1
We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph D, an injective overlap labeling assigns a unique stri…
On the representation of de Bruijn graphs
Rayan Chikhi, Antoine Limasset, Shaun Jackman +2
The de Bruijn graph plays an important role in bioinformatics, especially in the context of de novo assembly. However, the representation of the de Bruijn graph in memory is a comp…
Informed and Automated k-Mer Size Selection for Genome Assembly
Rayan Chikhi, Paul Medvedev
Genome assembly tools based on the de Bruijn graph framework rely on a parameter k, which represents a trade-off between several competing effects that are difficult to quantify. T…
Shortest paths between shortest paths and independent sets
Marcin Kaminski, Paul Medvedev, Martin Milanic
We study problems of reconfiguration of shortest paths in graphs. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-…
The Plane-Width of Graphs
Marcin Kaminski, Paul Medvedev, Martin Milanic
Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the…