MOTIVATION: The Optical Mapping System discovers structural variants and potentiates sequence assembly of genomes via scaffolding and comparisons that globally validate or correct sequence assemblies. Despite its utility, there are few publicly available tools for aligning optical mapping datasets. RESULTS: Here we present software, named 'Maligner', for the alignment of both single molecule restriction maps (Rmaps) and in silico restriction maps of sequence contigs to a reference. Maligner provides two modes of alignment: an efficient, sensitive dynamic programming implementation that scales to large eukaryotic genomes, and a faster indexed based implementation for finding alignments with unmatched sites in the reference but not the query. We compare our software to other publicly available tools on Rmap datasets and show that Maligner finds more correct alignments in comparable runtime. Lastly, we introduce the M-Score statistic for normalizing alignment scores across restriction maps and demonstrate its utility for selecting high quality alignments. AVAILABILITY AND IMPLEMENTATION: The Maligner software is written in C ++ and is available at https://github.com/LeeMendelowitz/maligner under the GNU General Public License. CONTACT: [email protected].

BACKGROUND: Genome assembly is difficult due to repeated sequences within the genome, which create ambiguities and cause the final assembly to be broken up into many separate sequences (contigs). Long range linking information, such as mate-pairs or mapping data, is necessary to help assembly software resolve repeats, thereby leading to a more complete reconstruction of genomes. Prior work has used optical maps for validating assemblies and scaffolding contigs, after an initial assembly has been produced. However, optical maps have not previously been used within the genome assembly process. Here, we use optical map information within the popular de Bruijn graph assembly paradigm to eliminate paths in the de Bruijn graph which are not consistent with the optical map and help determine the correct reconstruction of the genome. RESULTS: We developed a new algorithm called AGORA: Assembly Guided by Optical Restriction Alignment. AGORA is the first algorithm to use optical map information directly within the de Bruijn graph framework to help produce an accurate assembly of a genome that is consistent with the optical map information provided. Our simulations on bacterial genomes show that AGORA is effective at producing assemblies closely matching the reference sequences.Additionally, we show that noise in the optical map can have a strong impact on the final assembly quality for some complex genomes, and we also measure how various characteristics of the starting de Bruijn graph may impact the quality of the final assembly. Lastly, we show that a proper choice of restriction enzyme for the optical map may substantially improve the quality of the final assembly. CONCLUSIONS: Our work shows that optical maps can be used effectively to assemble genomes within the de Bruijn graph assembly framework. Our experiments also provide insights into the characteristics of the mapping data that most affect the performance of our algorithm, indicating the potential benefit of more accurate optical mapping technologies, such as nano-coding.

MOTIVATION: Genomic mutations and variations provide insightful information about the functionality of sequence elements and their association with human diseases. Traditionally, variations are identified through analysis of short DNA sequences, usually shorter than 1000 bp per fragment. Optical maps provide both faster and more cost-efficient means for detecting such differences, because a single map can span over 1 million bp. Optical maps are assembled to cover the whole genome, and the accuracy of assembly is critical. RESULTS: We present a computationally efficient model-based method for improving quality of such assemblies. Our method provides very high accuracy even with moderate coverage (<20 x). We utilize a hidden Markov model to represent the consensus map and use the expectation-Maximization algorithm to drive the refinement process. We also provide quality scores to assess the quality of the finished map. AVAILABILITY: Code is available from www.cmb.usc.edu/people/valouev/

Current moIecuIar bioIogy techniques were deveIoped primarily for characterization of single genes, not entire genomes, and, as such, are not ideally suited to high resolution analysis of complex traits and the moiecular genetics of very large populations.Despite rapid progress in the human genome project effort, there is little doubt that radicaIIy new conceptual approaches are needed before routine whole genome-based analyses can be undertaken by both basic research and clinical laboratories.Physical mapping of genomes, using restriction endonucleases, has played a major role in the identification and characterizing various loci, for example, by aiding clone contig formation and by characterizing genetic lesions.Restriction maps provide precise genomic distances, unlike ordered sequencebased landmarks such as Sequence Tagged Sites (ST%), that are essential for optimizing the efficiency of sequencing efforts, and for determining the spatial relationships of specific loci.When compared to tedious hybridization-based fingerprinting approaches, ordered restriction maps offer relatively unambiguous clone characterization that is useful in contig formation, establishment of minimal tiling paths for sequencing, and preliminary characterization of sequence lesions.In addition, such maps provide a useful scaffold for sequence assembly, often critical in the final sequence finishing stage.Despite the broad applications of restriction maps, the associated techniques for their generation have changed little over the last ten years, primarily because they still utilize electrophoretic analysis.To help overcome these shortcomings, our laboratory developed the first practical non-electrophoretic genomic mapping approach, Optical Mapping, to meet this need.Optical Mapping is a single molecule methodology for the rapid production of ordered restriction