Fast and accurate correction of optical mapping data via spaced seeds

PerFSeeB: designing long high-weight single spaced seeds for full sensitivity alignment with a given number of mismatches

BACKGROUND

Technical progress in computational hardware allows researchers to use new approaches for sequence alignment problems. For a given sequence, we usually use smaller subsequences (anchors) to find possible candidate positions within a reference sequence. We may create pairs ("position", "subsequence") for the reference sequence and keep all such records without compression, even on a budget computer. As sequences for new and reference genomes differ, the goal is to find anchors, so we tolerate differences and keep the number of candidate positions with the same anchors to a minimum. Spaced seeds (masks ignoring symbols at specific locations) are a way to approach the task. An ideal (full sensitivity) spaced seed should enable us to find all such positions subject to a given maximum number of mismatches permitted.

RESULTS

Several algorithms to assist seed generation are presented. The first one finds all permitted spaced seeds iteratively. We observe specific patterns for the seeds of the highest weight. There are often periodic seeds with a simple relation between block size, length of the seed and read. The second algorithm produces blocks for periodic seeds for blocks of up to 50 symbols and up to nine mismatches. The third algorithm uses those lists to find spaced seeds for reads of an arbitrary length. Finally, we apply seeds to a real dataset and compare results for other popular seeds.

CONCLUSIONS

PerFSeeB approach helps to significantly reduce the number of reads' possible alignment positions for a known number of mismatches. Lists of long, high-weight spaced seeds are available in Additional file 1. The seeds are best in weight compared to seeds from other papers and can usually be applied to shorter reads. Codes for all algorithms and periodic blocks can be found at https://github.com/vtman/PerFSeeB .

Finding Overlapping Rmaps via Clustering

Optical mapping has been largely automated, and first produces single molecule restriction maps, called Rmaps, which are assembled to generate genome wide optical maps. Since the location and orientation of each Rmap is unknown, the first problem in the analysis of this data is finding related Rmaps, i.e., pairs of Rmaps that share the same orientation and have significant overlap in their genomic location. Although heuristics for identifying related Rmaps exist, they all require quantization of the data which leads to a loss in the precision. In this paper, we propose a Gaussian mixture modelling clustering based method, which we refer to as O, that finds overlapping Rmaps without quantization. Using both simulated and real datasets, we show that OMclust substantially improves the precision (from 48.3% to 73.3%) over the state-of-the art methods while also reducing CPU time and memory consumption. Further, we integrated OMclust into the error correction methods (Elmeri and Comet) to demonstrate the increase in the performance of these methods. When OMclust was combined with Comet to error correct Rmap data generated from human DNA, it was able to error correct close to 3x more Ramps, and reduced the CPU time by more than 35x.

Space-Efficient Indexing of Spaced Seeds for Accurate Overlap Computation of Raw Optical Mapping Data

A key problem in processing raw optical mapping data (Rmaps) is finding Rmaps originating from the same genomic region. These sets of related Rmaps can be used to correct errors in Rmap data, and to find overlaps between Rmaps to assemble consensus optical maps. Previous Rmap overlap aligners are computationally very expensive and do not scale to large eukaryotic data sets. We present Selkie, an Rmap overlap aligner based on a spaced (l,k)-mer index which was pioneered in the Rmap error correction tool Elmeri. Here we present a space efficient version of the index which is twice as fast as prior art while using just a quarter of the memory on a human data set. Moreover, our index can be used for filtering candidates for Rmap overlap computation, whereas Elmeri used the index only for error correction of Rmaps. By combining our filtering of Rmaps with the exhaustive, but highly accurate, algorithm of Valouev et al. (2006), Selkie maintains or increases the accuracy of finding overlapping Rmaps on a bacterial dataset while being at least four times faster. Furthermore, for finding overlaps in a human dataset, Selkie is up to two orders of magnitude faster than previous methods.

Determining Optical Mapping Errors by Simulations

MOTIVATION

Optical mapping is a complementary technology to traditional DNA sequencing technologies, such as next-generation sequencing (NGS). It provides genome-wide, high-resolution restriction maps from single, stained molecules of DNA. It can be used to detect large and small structural variants, copy number variations, and complex rearrangements. Optical mapping is affected by different kinds of errors in comparison with traditional DNA sequencing technologies. It is important to understand the source of these errors and how they affect the obtained data. This paper proposes a novel approach to modeling errors in the data obtained from the Bionano Genomics Inc. Saphyr system with Direct Label and Stain (DLS) chemistry. Some studies have already adressed this issue for older instruments with nicking enzymes, but we are unaware of a study that addresses this new system.

RESULTS

The main result is a framework for studying errors in the data obtained from the Saphyr instrument with DLS chemistry. The framework's main component is a simulation that computes how major sources of errors for this instrument (a false site, a missing site, and resolution errors) affect the distribution of fragment lengths in optical maps. The simulation is parametrized by variables describing these errors and we are using a differential evolution algorithm to evaluate parameters that best fit the data from the instrument. Results of the experiments manifest that this approach can be used to study errors in the optical mapping data analysis.

AVAILABILITY

Source codes supporting the presented results are available at: https://github.com/mvasinek/olgen-om-error-prediction. The data underlying this article are available on the Bionano Genomics Inc. website, at: https://bionanogenomics.com/library/datasets/.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Advances in optical mapping for genomic research

Recent advances in optical mapping have allowed the construction of improved genome assemblies with greater contiguity. Optical mapping also enables genome comparison and identification of large-scale structural variations. Association of these large-scale genomic features with biological functions is an important goal in plant and animal breeding and in medical research. Optical mapping has also been used in microbiology and still plays an important role in strain typing and epidemiological studies. Here, we review the development of optical mapping in recent decades to illustrate its importance in genomic research. We detail its applications and algorithms to show its specific advantages. Finally, we discuss the challenges required to facilitate the optimization of optical mapping and improve its future development and application.