algorithm

SeqBIM workshop 2020

Two talks from our group at SeqBIM next on November 24th.

SOFSEM 2021 program committee participation

PC membership

Superstring

Algorithms for shortest superstring questions

Fast_place

Software for efficient metagenomics and applications to virus metagenomics

New algorithm for the HOG

In collaboration with Prof. K. Park and Dr. S. Park, from the Seoul National University, in Southern Korea, we propose a new, efficient algorithm to build the Hierarchical Overlap Graph (HOG). This graph stores succinctly the ways overlapping reads can be merged to build superstrings. The article has been accepted for publication at SPIRE 2020 (see https://www.cs.ucf.edu/spire2020/index.php/accepted-papers/).

Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding

The boom of genomic sequencing makes compression of sets of sequences inescapable. This underlies the need for multi-string indexing data structures that helps compressing the data. The most prominent example of such data structures is the …

Fast and Accurate Genome-Scale Identification of DNA-Binding Sites

Discovering DNA binding sites in genome sequences is crucial for understanding genomic regulation. Currently available computational tools for finding binding sites with Position Weight Matrices of known motifs are often used in restricted genomic …

Superstring Graph: A New Approach for Genome Assembly

With the increasing impact of genomics in life sciences, the inference of high quality, reliable, and complete genome sequences is becoming critical. Genome assembly remains a major bottleneck in bioinformatics: indeed, high throughput sequencing …

Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings

Covering a directed graph by a Hamiltonian path or a set of words by a superstring belong to well studied optimisation problems that prove difficult to approximate. Indeed, the Maximum Asymmetric Travelling Salesman Problem (Max-ATSP), which asks for …

Combinatorics of Periods in Strings

We consider the set Γ(n) of all period sets of strings of length n over a finite alphabet. We show that there is redundancy in period sets and introduce the notion of an irreducible period set. We prove that Γ(n) is a lattice under set inclusion and …