Source author record

Christina Boucher

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Genomics Quantitative Methods Computational Engineering, Finance, and Science

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

PHONI: Streamed Matching Statistics with Multi-Genome References

Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database.

preprint2020arXiv

PFP Data Structures

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string $S$ , it produces a dictionary $D$ and a parse $P$ of overlapping phrases such that $\mathrm{BWT} (S)$ can be computed from $D$ and $P$ in time and workspace bounded in terms of their combined size $|\mathrm{PFP} (S)|$ . In practice $D$ and $P$ are significantly smaller than $S$ and computing $\mathrm{BWT} (S)$ from them is more efficient than computing it from $S$ directly, at least when $S$ consists of genomes from individuals of the same species. In this paper, we consider $\mathrm{PFP} (S)$ as a {\em data structure} and show how it can be augmented to support the following queries quickly, still in $O (|\mathrm{PFP} (S)|)$ space: longest common extension (LCE), suffix array (SA), longest common prefix (LCP) and BWT. Lastly, we provide experimental evidence that the PFP data structure can be efficiently constructed for very large repetitive datasets: it takes one hour and 54 GB peak memory for $1000$ variants of human chromosome 19, initially occupying roughly 56 GB.

preprint2015arXiv

Relative Select

Motivated by the problem of storing coloured de Bruijn graphs, we show how, if we can already support fast select queries on one string, then we can store a little extra information and support fairly fast select queries on a similar string.

preprint2014arXiv

Misassembly Detection using Paired-End Sequence Reads and Optical Mapping Data

A crucial problem in genome assembly is the discovery and correction of misassembly errors in draft genomes. We develop a method that will enhance the quality of draft genomes by identifying and removing misassembly errors using paired short read sequence data and optical mapping data. We apply our method to various assemblies of the loblolly pine and Francisella tularensis genomes. Our results demonstrate that we detect more than 54% of extensively misassembled contigs and more than 60% of locally misassembed contigs in an assembly of Francisella tularensis, and between 31% and 100% of extensively misassembled contigs and between 57% and 73% of locally misassembed contigs in the assemblies of loblolly pine. MISSEQUEL can be downloaded at http://www.cs.colostate.edu/seq/.

preprint2014arXiv

Variable-Order de Bruijn Graphs

The de Bruijn graph $G_K$ of a set of strings $S$ is a key data structure in genome assembly that represents overlaps between all the $K$ -length substrings of $S$ . Construction and navigation of the graph is a space and time bottleneck in practice and the main hurdle for assembling large, eukaryote genomes. This problem is compounded by the fact that state-of-the-art assemblers do not build the de Bruijn graph for a single order (value of $K$ ) but for multiple values of $K$ . More precisely, they build $d$ de Bruijn graphs, each with a specific order, i.e., $G_{K_1}, G_{K_2}, ..., G_{K_d}$ . Although, this paradigm increases the quality of the assembly produced, it increases the memory by a factor of $d$ in most cases. In this paper, we show how to augment a succinct de Bruijn graph representation by Bowe et al. (Proc. WABI, 2012) to support new operations that let us change order on the fly, effectively representing all de Bruijn graphs of order up to some maximum $K$ in a single data structure. Our experiments show our variable-order de Bruijn graph only modestly increases space usage, construction time, and navigation time compared to a single order graph.

preprint2012arXiv

On Approximating String Selection Problems with Outliers

Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of same-length strings, and a parameter d, find a string x that maximizes the number of "non-outliers" within Hamming distance d of x. We prove this problem has no PTAS unless ZPP=NP, correcting a decade-old mistake. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no EPTAS unless W[1]=FPT. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult.

preprint2012arXiv

SeeSite: Efficiently Finding Co-occurring Splice Sites and Exon Splicing Enhancers

The problem of identifying splice sites consists of two sub-problems: finding their boundaries, and characterizing their sequence markers. Other splicing elements---including, enhancers and silencers---that occur in the intronic and exonic regions play an important role in splicing activity. Existing methods for detecting splicing elements are limited to finding either splice sites or enhancers and silencers, even though these elements are well-known to co-occur. We introduce SeeSite, an efficient and accurate tool for detecting splice sites and their complementary exon splicing enhancers (ESEs). SeeSite has three stages: graph construction, finding dense subgraphs, and recovering splice sites and ESEs along with their consensus. The third step involves solving Consensus Sequence with Outliers, an NP-complete string clustering problem. We prove that our algorithm for this problem outputs near-optimal solutions in polynomial time. Using SeeSite we demonstrate that ESEs are preferentially associated with weaker splice sites, and splice sites of a certain canonical form co-occur with specific ESEs.

preprint2011arXiv

Outlier Detection for DNA Fragment Assembly

Given $n$ length- $\ell$ strings $S =\{s_1, ..., s_n\}$ over a constant size alphabet $Σ$ together with parameters $d$ and $k$ , the objective in the {\em Consensus String with Outliers} problem is to find a subset $S^*$ of $S$ of size $n-k$ and a string $s$ such that $\sum_{s_i \in S^*} d(s_i, s) \leq d$ . Here $d(x, y)$ denotes the Hamming distance between the two strings $x$ and $y$ . We prove 1. a variant of {\em Consensus String with Outliers} where the number of outliers $k$ is fixed and the objective is to minimize the total distance $\sum_{s_i \in S^*} d(s_i, s)$ admits a simple PTAS. (ii) Under the natural assumption that the number of outliers $k$ is small, the PTAS for the distance minimization version of {\em Consensus String with Outliers} performs well. In particular, as long as $k\leq cn$ for a fixed constant $c < 1$ , the algorithm provides a $(1+ε)$ -approximate solution in time $f(1/ε)(n\ell)^{O(1)}$ and thus, is an EPTAS. 2. In order to improve the PTAS for {\em Consensus String with Outliers} to an EPTAS, the assumption that $k$ is small is necessary. Specifically, when $k$ is allowed to be arbitrary the {\em Consensus String with Outliers} problem does not admit an EPTAS unless FPT=W[1]. This hardness result holds even for binary alphabets. 3. The decision version of {\em Consensus String with Outliers} is fixed parameter tractable when parameterized by $\frac{d}{n-k}$ . and thus, also when parameterized by just $d$ . To the best of our knowledge, {\em Consensus String with Outliers} is the first problem that admits a PTAS, and is fixed parameter tractable when parameterized by the value of the objective function but does not admit an EPTAS under plausible complexity assumptions.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.