# Fast genomic optical map assembly algorithm using binary representation

Przemysław Stawczyk and Robert Nowak
Institute of Computer Science, Warsaw University of Technology,
Warsaw, Poland

(2022.10.12)

###### Abstract

Reducing the cost of sequencing genomes provided by next-generation sequencing
technologies has greatly increased the number of genomic projects. As a
result, there is a growing need for better assembly and assembly validation
methods. One promising idea is to use heterogeneous data in assembly projects.
Optical Mapping (OM) is beneficial in validating genomic assemblies,
correction and scaffolding. Single raw OM read describes a DNA molecule’s long
fragment, up to 1Mbp. Raw OM data from the same genome could be assembled to
create consensus maps that span an entire chromosome. The assembly process is
computationally hard because of the large number of errors in input data. This
work describes a new algorithm and computer program to assemble OM reads
without a reference genome. In our algorithm, we explored binary
representation for genome maps. We focused on the efficiency of data
structures and algorithms and scale on parallel platforms. The algorithm
consists of several steps, of which the most important are : (1) conversion of
the restriction maps into binary strings, (2) detection of overlaps between
restriction maps, (3) determining the layout of restriction maps set, (4)
creation of consensus genomic maps. Our algorithm deals with optical mapping
data with low error levels but fails with high-level error reads. We developed
a software library, console application and module for Python language. The
approach presented in this paper proved to be faster than a dynamic
programming approach and performed well on error-free data. It could be used
as a step of de novo assembly pipelines or to detect misassemblies. The
software is freely available in a public repository under GNU LGPL v3 license
(https://sourceforge.net/p/binary-genome-maps/code).

111Further author information: (Send correspondence to Robert Nowak) Robert
Nowak: Tel: +48 22 2347718; E-mail<EMAIL_ADDRESS>
#### Keywords:

optical mapping; genome mapping; consensus; next generation sequencing.

##  1 Introduction

Reducing the cost of sequencing genomes has greatly increased the number of
genomic projects and raw read data available. Better sequencing results have
been enabled by better software for assembly and scaffolding. More efficient
algorithms can properly use the increasing volume of available data. With data
from different sequencing technologies, Heterogeneous sequencing is an
effective method of improving sequencing results. We propose that optical
mapping results be included in heterogeneous sequencing.

Optical Mapping (OM) has been found to be very useful in structural variation
analysis, validating genomic assemblies [21], correction and scaffolding
assembled contigs [4, 6]. In the OM process, DNA is first isolated before
nicking enzymes are used to digest DNA strands [25]. The digested DNA is later
imaged [20] to determine the distances between the labels on a DNA strand. The
process generates information about the placement of label sites on DNA
strands, referred to as restriction maps (rmaps). Rmaps are analogous to
sequence reads in the context of genome sequencing and have a length of 150Kbp
– 1.6Mbp [18]. Rmaps can be assembled to create consensus maps. The result of
such an assembly can cover an entire chromosome. Some of the best-known
companies currently developing OM methods are Bionano Genomics [1]and Nabsys
[15].

Other than proprietary software from sequencer manufacturers, few algorithms
for creating whole-genome maps have been developed. Past projects have been
based upon dynamic programming with backtracking [11] which scales very poorly
with larger genomes, such as the human genome. Newer algorithms have been
developed only for resequencing assembly projects, as they require reference
map[9, 12].

In our new algorithm, we explore the possibility of using different genome map
representations by binary strings. Although this algorithm is more sensitive
to incorrect indexes of marker positions, it could be used in de novo
assemblies, as it does not require a reference genome or reference maps. Our
assembly algorithms could be executed on high-parallel platforms – we have
focused on efficiency and the ability to scale with parallel execution. The
software library and application were developed in C++ and are freely
available as open-source.

##  2 Materials and methods

Our assembly algorithm is based on an overlap-layout-consensus model. It uses
a binary representation of genomic maps, enabling efficient computational
resources. Short binary sequences can be easily compared using an XOR
operation directly implemented in every modern processor. The algorithm
consists of four steps:

  * •

Converting rmaps to binary string.

  * •

Overlap detection – scoring the similarities of each pair of rmaps.

  * •

Layout forming – resolving conflicts in neighbouring rmaps.

  * •

Consensus – constructing the contiguous output.

The algorithm steps are described below.

### Genomic map representation

A restriction map (rmap) is a set of marker positions relative to a genome
fragment. A consensus genome map is created during assembly from rmaps for the
same genome or chromosome. The representation of a consensus genome map and a
single restriction map is similar. It is an ordered set of marker positions
relative to the beginning of a genome fragment or chromosome. We propose a new
representation based on quantization and binary sequences. Each position in a
binary sequence represents a constant genome fragment called a quant, the
length of each quant is the same. ’1’ in the sequence indicates at least one
marker present in the quant, while ’0’ indicates no markers. We depict such a
representation in Figure 1.

Figure 1: Genome map representations (example for a genome of size 4000). a.–
genome with markers marked in red, b. – distances between markers, c. – marker
positions, d. – binary map for quant size = 100.

Converting a rmap into a binary string leads to a loss of information, namely,
the exact relative positions of the markers. We call this issue a quantization
error. Rmaps from the same genome fragment quantized with the same quant
length can produce different binary string representations. The different
placement of quant borders results in the relative placement of markers in
binary sequence representations. Moreover, two markers close to each other can
be represented as one bit or two neighbour bits. We present a simple example
of such differences in Figure 2. These effects are less pronounced with low
marker density but must be accounted for in an algorithm.

Figure 2: Quantization errors visualization. a. – aligned maps from the same
genome fragment, b. – aligned maps from a. quantized with quant length 4, c. –
aligned maps from a. quantized with quant length 5.

We assume some level of difference between two rmaps, even if they are in
silico generated error-free rmaps. However, quantization has been used
successfully in genome mapping projects, and quantized maps are still found
useful [9, 13].

### Overlap detection

After converting rmaps into binary strings, the similarity scores for all
pairs of rmaps are calculated. The similarity scoring is the most time-
consuming step due to the high number of rmaps produced in a single
experiment.

The binary string representation of rmaps allows a very fast scoring of the
similarity of two rmaps in the overlaps detection step. The algorithm should
find the score for the best matching prefix of one rmap to the suffix of the
second rmap. In our approach, for each offsets inside$<-n/2,+n/2>$, n is the
length of the binary string the binary exclusive or (XOR) operation is
performed. XOR returns ’1’ when there is a difference at a given position,
while ’0’ indicate confirmation, as depicted in Figure 3. The XOR operation is
implemented as a single instruction between registers in all general-purpose
CPUs. Therefore, our algorithm is very fast because it uses operations
implemented directly in the hardware. The number of differences (number of ’1’
returned by XOR) determines a map’s similarity for a given offset. We present
our approach to overlap detection in Algorithm 1.

Figure 3: Visualization of two rmaps overlaps and XOR results. In map red
indicates marker, blue – no marker. In results, red indicates difference,
green – no difference. a. – incorrect alignment, 10 differences; b. – perfect
alignment, no differences. Algorithm 1 Overlap search for left neighbor

1:function findLeftAlignment(ref, aligned)

2: $maxShift\leftarrow\textsc{minLen}(ref,aligned)$

3:$\triangleright$ could be adjusted to be e.g. half of smaller rmap

4: $bestAlign\leftarrow 1$

5:$\triangleright$ differenting part, 1 means that all bits differ, 0 means
full conformance.

6: $bestShift\leftarrow 0$

7:$\triangleright$ shift between rmaps ends

8: for $shift\in\\{1,...,maxShift\\}$ do

9: $test\leftarrow aligned\ll shift$

10: $result\leftarrow test\textsc{ xor }ref$

11: $\textsc{truncateLonger}(test,ref)$

12: if $\textsc{count}(result)$ / $\textsc{len}(result)<bestAlign$ then

13:$\triangleright$ it’s a better alignment

14: $bestAlign\leftarrow\textsc{count}(result)$ / $\textsc{len}(result)$

15: $bestShift\leftarrow shift$ return $bestShift$

### Layout forming

Our analysis of multiple genomes and enzymes shows that the markers density is
similar. As mentioned in the ’Genomic map representation’ subsection, a binary
representation loses information. In an extreme case (quant length is too
big), the binary string is ’11…1’ (only ’1’). We assume that the binary string
represents a given rmap, so it has at most 10% of ’1’. This assumption could
be easily fulfilled - we could decrease the quant size if we had too much 1.
Using this assumption, we can consider in layout formatting only rmaps with
differences below a given threshold and with overlaps above a given length.
For example, if maps have an average density of markers around 10%, rmaps
aligned with more than 10% of differences can be discarded. We selected the
threshold of 10% experimentally so that the length of binary strings did not
increase the computation time too much. Our algorithm has a parameter that
allows the end-user to set another value. We commonly set this value to 20%,
or even 30% in numerical experiments, also allowing less precise alignments.

Our method for layout determination is presented as Algorithm 2.

Algorithm 2 Global rmaps alignment

1:procedure findGlobalAlignment(rmaps)

2: for $i\in\\{0,1...\textsc{len}(rmaps)\\}$ do

3: $smallestShift\leftarrow\textsc{len}(rmaps[i])$

4: $leftRMap\leftarrow i$

5: for $j\in\\{0,1...\textsc{len}(rmaps)\\}$ do

6: if $i==j$ then

7: continue

8: $result\leftarrow\textsc{findLeftAlignment}(rmaps[i],rmaps[j])$

9: if $smallestShift>result$ then

10: $smallestShift\leftarrow result$

11: $leftRMap\leftarrow j$

12: $rmaps[i].addLeftNeighbor(leftRMap)$

After rmaps are detected as neighbours we prepare them for alignment. We
eliminate rmaps containing themselves entirely in others. We present a
visualization of rmaps layouts in Figure 4.

Figure 4: Visualization of aligned rmaps. Red indicates marker in map, blue
indicates no marker. a. – reference map, b. – set of aligned rmaps.

### Consensus map creation

Contiguous sequences of neighbour rmaps are constructed after aligning all the
maps. For contigs detection, we interrogate the graph, where rmaps are the
vertex, and the similarity score is the edge. If several vertices form a line,
these vertices are traversed using a consensus algorithm. If several vertices
form a circle on a graph, the circle is broken.

Each sequence of rmaps is traversed using a consensus algorithm to create a
contiguous map representation. For each position on the aligned rmaps, the
number of ’1’ and ’0’ are counted, then the most frequent symbol is chosen. In
the case of an equal number of ’1’ and ’0’, the symbol ’1’ is chosen because
the rmap representation is sparse and losing information about a marker is
considered a more significant issue than adding a non-existing marker. We
present this process in Algorithm 3.

Algorithm 3 Consensus algorithm

1:function performConsensus(contig)

2: $map\leftarrow$ [ ]

3: $count\leftarrow 0$

4: for $p\in\\{0,1,...,\textsc{len}(contig)-1\\}$ do

5:$\triangleright$ p \- position from beginning of overlapping maps

6: for $rmap\in\textsc{mapsAtPos}(contig,p)$ do

7: if $rmap.at(p)==1$ then $\triangleright$ rmap.at(p) - value on position p

8: $count\leftarrow count+1$

9: if $count<(k/2)$ then

10: $map.append(0)$

11: else

12: $map.append(1)$ return $map$

### Assembly parameters

Our application allows users to adjust certain parameters of the assembly:

  * •

margin quant – the minimal length of overlap (i. e., common fragment of rmaps
pair) in quants.

  * •

margin part – minimal part of the smaller map to consider for overlap (i. e.
if the margin is 0.25, the overlap has to be at least 25% of smaller map
length in size)

  * •

threshold – the threshold of differences to consider an overlap meaningful (i.
e. if the threshold is 0.15, overlaps with more than 15% of differences on the
common part are discarded)

  * •

marker preference – consensus preference, symbol to be used in resulting
contig if there are 50% of both ’0’ and ’1’

  * •

folds – how many times assembly step has to be performed before giving output.

Users can also adjust input and output filenames and the number of threads
used. BGM is open source, and the assembly process is modular. For example,
further adjustments can be made by changing the cost function in the source
code.

##  3 Results

We performed numerical experiments on simulated and real datasets. We compared
our approach with an algorithm based on dynamic programming with backtracking.
Moreover, we analyzed the computational complexity of our new algorithm. In
our experiments we used data from three organisms : Escherichia coli [5],
Caenorhabditis elegans [2], and Acinetobacter baumannii [10]. We provide a
brief genome sizes summary of the species used in Table 1.

Table 1: Summary of genome sizes and chromosomes count. species | chromosomes | length [Mbp]
---|---|---
E. coli | 1 | 4.6
C. elegans | 7 | 100.2
A. baumannii | 1 | 3.8

### Simulated data

We simulated error-free rmaps using a reference genome. The rmaps length was
sampled with the normal distribution of a given mean and standard deviation,
and the rmaps position was sampled using a uniform distribution. Marker
positions were then calculated, with fragments on the ends bearing no markers
being removed. Finally, the rmap was quantized with a given quant value (1000
bp in our case). An example of a simulated dataset aligned to a reference
genome is presented in Figure 5.

Figure 5: Visualization of simulated rmaps dataset aligned to a reference
genome. The reference genome is marked in green, the rmaps in blue and markers
are denoted with red. Rmaps come from the E. coli genome for the BspQI enzyme
and $15\times$ coverage.

Using simulated datasets from the E. coli genome [5] we reconstructed the
whole genome consensus map, with simulated BspQI marker and $7.5\times$
coverage of the genome. For BssSI markers we reconstructed the whole genome
for $10\times$ coverage. Both datasets are summarized in Table 2.

Table 2: Input data that enabled reconstruction of a whole E. coli reference map. enzyme | coverage | rmap count | avg length [Kbp]
---|---|---|---
BspQI | 7.5 | 36 | 959.30
BssSI | 10 | 47 | 1093.00

The the experiment result is visualized in Figure 6.

Figure 6: Visualization of assembly results for simulated E. coli dataset for
BspQI simulated enzyme with $7.5\times$ coverage. Reference genome is marked
in green, result in blue and markers are denoted by red.

### Tuning cost function for overlapping

We analyzed the best overlap using two different cost functions:

  1. 1.

Number of differences on the overlapping fragment.

  2. 2.

Differentiating level calculated as the number of differences divided by
overlap length.

For comparison, we generated four datasets. Rmap length was sampled from a
normal distribution with an expected value of 1 Mbp and a standard deviation
of 300 Kbp. The datasets statistics are summarized in Table 3. We only changed
the cost function during our experiments, leaving the remaining parameters
unaltered. The parameters used in this experiment were : margin_part = 0.5,
margin_quant = 100, folds = 2, thresh = 0.1. The comparison was run on
simulated datasets from E. coli [5] and C. elegans [2] reference genomes. The
results of our experiments are also summarized and presented in Table 4.

Table 3: Input data for cost function experiments genome | enzyme | coverage | rmap count | avg. rmap length [Kbp]
---|---|---|---|---
E. coli | BspQI | 10 | 47 | 983.38
E. coli | BspQI | 20 | 92 | 1003.08
C. elegans | BssSI | 10 | 967 | 1031.72
C. elegans | BssSI | 40 | 3943 | 1008.60
Table 4: Results of cost function experiments function | dataset | contigs | avg. length | N50 | longest contig
---|---|---|---|---|---
|  | count | [Kbp] | [Kbp] | [Kbp]
1 |  E. coli, BspQI 10x | 2 | 3167 | 4212 | 4212
2 |  E. coli, BspQI 10x | 2 | 3387 | 4633 | 4633
1 |  E. coli, BspQI 20x | 3 | 2748 | 4633 | 4633
2 |  E. coli, BspQI 20x | 3 | 2497 | 4633 | 4633
1 |  C. elegans, BssSI 10x | 79 | 2982 | 2413 | 8436
2 |  C. elegans, BssSI 10x | 80 | 3056 | 2375 | 7242
1 |  C. elegans, BssSI 40x | 38 | 11984 | 5263 | 17718
2 |  C. elegans, BssSI 40x | 41 | 11221 | 4985 | 20769

All rmaps were aligned with at least one other. After analyzing the results,
we found that the second function, when the cost was calculated as the number
of differences divided by the overlap length, allowed us to connect rmaps more
effectively. We decided to use this function in further experiments.

### Comparing results of our algorithm with dynamic programming approach

We compared our algorithm to a dynamic programming approach with backtracking
[22, 23]. We ran both algorithms on a single thread for comparison purposes,
and parameters were unchanged for all runs. We used a server with a Xeon
E5-2637 v2 processor (2 cores 4 threads, 3.5 GHz [7]). The comparison was run
on simulated datasets from E. coli [5] and C. elegans [2] reference genomes.
We compared performance and quality, measured as run times and the number of
contigs. We ran software with a dynamic programming approach developed by
Valouev et al [24].

Figure 7 summarizes the contigs produced by both algorithms on the E. coli
dataset. We assume rmaps without gaps cover the input genome (Lander-Waterman
theory [8] for genomes used, coverages and rmap sizes). Therefore, we measure
the quality of alignment as a number of contigs. The smaller the number of
contigs, the better.

The dynamic programming approach needed twice as much coverage to produce a
contig with BspQI than our approach did. When simulating BssSI markers, our
algorithm reconstructed the whole genome map with $10\times$ coverage, whereas
the dynamic programming approach did not produce any contig at all, even with
$40\times$ coverage. Due to this, we simulated only the BspQI enzyme when
comparing algorithms on the C. elegans genome [2]. A summary of the contigs
counts during our experiments with the simulated C. elegans dataset is
presented in Figure 7.

Figure 7: Comparison of contigs count depending on coverage of the genome, E.
coli dataset (on top), C. elegans dataset (on bottom).

Our experiments show that an algorithm based on binary strings can reconstruct
a whole genome with less coverage. The parameters need to be tuned to a
specific dataset for best results.

We measured the time needed for both algorithms to finish the assembly. The
results are summarized in Figure 8. From all runs, we can see that our
approach delivered results around 80 times faster than the dynamic approach on
the datasets tested. The complexity of both algorithms is $\Omega(n^{2})$
because each rmap must be analyzed individually, and in both cases, the
algorithm must seek an overlap with another rmap.

Figure 8: Comparison of time needed for algorithms to finish assembly
depending on genome coverage of E. coli dataset (on left), and C. elegants
dataset (on right).

###  3.1 Experiments with exponential rmaps length distribution

We performed an additional experiment using datasets where length was
generated using exponential distribution with parameter
$\beta=150kbp$222$\beta$ is the scale parameter, which is the inverse of the
rate parameter $\beta=1/\lambda$. The rate parameter is an alternative, widely
used parameterization of the exponential distribution. Maps shorter than 100
kbp were discarded, resulting in 275 kbp average length of an rmap. Datasets
used were summarized in Table 5.

Table 5: Summary of exponential length datasets enzyme | coverage | map count | avg. length [kbp]
---|---|---|---
BssSI | 10 | 173 | 258.73
BssSI | 20 | 320 | 279.92
BssSI | 30 | 484 | 277.45
BssSI | 40 | 651 | 274.58
BssSI | 60 | 965 | 277.94
BspQI | 10 | 170 | 261.48
BspQI | 20 | 316 | 281.67
BspQI | 30 | 480 | 277.30
BspQI | 40 | 643 | 276.26
BspQI | 60 | 957 | 278.38

We were able to reconstruct the whole E. coli genome map using $30\times$
coverage, both with BspQI and BssSI enzymes simulation. We obtained whole
genome maps using parameters : margin_part = 0.3, margin_quant = 90, thresh =
0.1. BspQI dataset required folds parameter to be set on 3 or more, where with
BssSI 2 was enough. The dynamic programming approach was able to reconstruct
the genome only with $60\times$ coverage and BspQI enzyme. There was also a
partial contig reconstructed with $60\times$ coverage and BssSI enzyme. Apart
from that, the dynamic programming approach produced no contigs.

### Experiments with real data

We performed experiments using a real dataset from the optical mapping of the
A. baumannii genome [10]. Rmaps from this dataset were converted into binary
form using segment lengths of 1000 bp and 1500 bp. We used the entire dataset
and subset containing only maps longer than 300 Kbp in both cases. A summary
of the datasets is presented in Table 6.

We could not create a consensus map with these datasets, despite changing the
parameters. For analysis, we used results from the original genomic project
[10] because the authors did not provide the information about the enzyme
used. The statistics of the two experiments on filtered datasets are presented
in Table 7.

Table 6: Summary of real datasets from A. baumannii used in experiments. dataset | rmap count | avg rmap length [Kbp]
---|---|---
all | 51389 | 214.67
rmapy longer than 300 Kbp | 7359 | 385.20
Table 7: Summary of experiments with real dataset from A. baumannii. margin_part | margin_quant | thresh | folds |  | contigs
---
count
| N50
---
[Kbp]
| avg contig
---
length [Kbp]
0.5 | 65 | 0.08 | 2 | 784 | 395 | 409.41
0.7 | 65 | 0.065 | 1 | 1176 | 408 | 426.99

Even though the dataset has around $725\times$ genome coverage, we could not
create valid contigs. During the experiments, we encountered two anomalies
that frequently occurred on the resulting contigs. Some of the maps had long
areas free from any markers not present on the reference map. An example of
such a contig is presented in Figure 9. The other anomaly in the results was a
significant increase in error frequency the longer the distance from the
correct fragment. An example of such an effect is presented in Figure 10.

Figure 9: Example of contig with empty space in centre. The reference map and
contig are presented in blue with red markers. The reference map is at the
top, the contig in the middle. The last row is a comparison where red
signifies difference and green signifies conformity. Figure 10: Example of
contig with errors at its ends. The reference map and contig are presented in
blue with red markers. The reference map is at the top and the contig in the
middle. The last row is a comparison where red signifies difference and green
signifies conformity.

We assume that most errors were caused by sizing errors and different stretch
factors of the molecules scanned. Our algorithm did not address such errors
due to the nature of binary sequences.

### Experiment on simulated A. baumannii

We performed experiments using a simulated dataset from the same species to
check if the genome sequences were not the source of the problems encountered
during our experiments with real datasets. We used the reference genome of the
bacteria[3] and generated rmaps datasets simulating nicking of BspQI and BssSI
enzymes. The length was sampled from a normal distribution with an expected
value of 400 Kbp and a standard deviation of 150 Kbp to match map lengths from
a filtered real dataset. We summarize the datasets created in Table 8. For
parameters margin_part = 0.3, margin_quant = 105, folds = 2, thresh = 0.19.
For rmaps generated simulating the BspQI enzyme we were able to obtain a
consensus map covering the whole genome. For rmaps generated using the enzyme,
greater sequencing coverage was necessary, and the folds parameter BssSI was
increased to $3$. We were also able to create whole-genome consensus maps
using datasets with higher (i. e. $40-70\times$) genome coverage.

Table 8: Summary of simulated datasets from A. baumannii used in experiments. enzyme | coverage | rmaps count | average length [Kbp]
---|---|---|---
BspQI | 25 | 244 | 391.53
BssSI | 25 | 244 | 397.07

##  4 Discussion

In our experiments, we were able to reconstruct the genomes of E. coli and C.
elegans from simulated error-free datasets. Our algorithm proved faster than a
dynamic programming approach and produced results with less genome coverage
needed. We used two different enzymes BspQI and BssSI to show that algorithm
results are similar for both cases. Our algorithm should work correctly for
any enzyme if the sites are spread over the genome.

Our approach can deal with quantization artefacts and the inaccuracy of
single-site placement. BGM can also deal with OM errors like false and missing
sites, which are present in a binary string as a flipped bit ’1’ instead of
’0’ and ’0’ instead of ’1’, respectively. Our algorithms deal with dose
mistakes and artefacts by allowing differences between rmap alignments. When
noise is more significant than a threshold (this is an algorithm parameter set
by the user), two noisy rmaps will not be connected. However, due to the
nature of binary strings, this approach cannot deal with other kinds of
errors, resulting in insertion, deletion, or shift in a binary string.
Examples of such errors are stretch variance, sizing errors and missing
fragments.

BGM creates a consensus restriction map on chromosome length and could be used
to find structural rearrangements. Moreover, BGM can be used as a hybrid de
novo assembly step. As presented in our previous work [16] a simultaneous use
of available sequencing technologies is useful in improving genome assemblies.
BGM algorithm deals with optical mapping data with low error level, e.g.
provided by nabsys [17].

With real datasets, our algorithm struggled to produce valid sequences. In our
opinion, this effect is due to sizing errors present in the optical mapping
data. Even a slightly stretched map of the same fragment of the genome could
not be aligned perfectly.

Our approach could be modified and used to align contigs on consensus maps as
both contigs and consensus maps have a low error rate. Another option is to
use correction algorithms [14, 19] focused on resolving to size and stretch
errors as a part of the assembly pipeline. BGM is fully open source and
available at https://sourceforge.net/projects/binary-genome-maps/. We would be
grateful if someone could adopt any correction algorithm or create a new one.
We also share all of the datasets mentioned and encourage the community to
perform experiments using our software. We are open to all contributions to
our project.

##  5 Conclusion

As more genome mapping and heterogeneous genomic projects are created, it is
crucial to develop open-source algorithms to deal with such data. To this end,
our paper presents an algorithm based on binary representation to create
consensus maps from rmaps. However, judging from the results of the
experiments, this algorithm is, in our opinion, better suited for applications
with error-free maps like contigs alignment.

## Availability and requirements

BGM is implemented in C++, and is freely available under GNU Library or Lesser
General Public License version 3.0 (LGPLv3). It and related materials (like
all datasets used) can be downloaded from project homepage
https://sourceforge.net/projects/binary-genome-maps/.

## Competing interests

The author declares that he has no competing interests.

## Author contributions

PS and RN Identified the problem and designed the approach., PS Implemented
the software, worked on testing and validation. PS Wrote the main manuscript
text and prepared figures. All authors read and approved the final manuscript.

## Acknowledgements

This research was funded by Warsaw University of Technology grant CyberiADa-1.

## References

  * [1] Bionano Genomics.  Bionano Genomics website.  https://bionanogenomics.com/.  Accessed 30 Sep 2021.
  * [2] C. elegans Sequencing Consortium.  Genome sequence of the nematode C. elegans: a platform for investigating biology, 12 1998.
  * [3] J. Farlow, M. Nozadze, N. Mitaishvili, A. Kotorashvili, N. Kotoria, K. Arobelidze, V. Tavadze, T. Simsive, P. Imnadze, N. Latif, M. P. Nikolich, M. Washington, M. K. Hinkle, P. Kwon, and N. Trapaidze.  Comparative genomic analysis of four multidrug-resistant isolates of acinetobacter baumannii from georgia, 2020.
  * [4] J. L. Fierst.  Using linkage maps to correct and scaffold de novo genome assemblies: methods, challenges, and computational tools.  Front Genet, 6:220, 2015.
  * [5] P. L. Freddolino, S. Amini, and S. Tavazoie.  Newly identified genetic variations in common Escherichia coli MG1655 stock cultures, 01 2012.
  * [6] K. Howe and J. M. Wood.  Using optical mapping data for the improvement of vertebrate genome assemblies.  GigaScience, 2015.
  * [7] intel.  Automated Relational Knowledge Base.  https://ark.intel.com/content/www/us/en/ark/products/75792/intel-xeon-processor-e52637-v2-15m-cache-3-50-ghz.html, 07 2013.
  * [8] E. S. Lander and M. S. Waterman.  Genomic mapping by fingerprinting random clones: a mathematical analysis.  Genomics, 2(3):231–239, 1988.
  * [9] A. K. Leung, T. P. Kwok, R. Wan, M. Xiao, P. Y. Kwok, K. Y. Yip, and T. F. Chan.  OMBlast: alignment tool for optical mapping using a seed-and-extend approach.  Bioinformatics, 33(3):311–319, 02 2017.
  * [10] A. K.-Y. Leung, M. C.-J. Liu, L. Li, Y. Y.-Y. Lai, C. Chu, P.-Y. Kwok, P.-L. Ho, K. Y. Yip, and T.-F. Chan.  OMMA enables population-scale analysis of complex genomic features and phylogenomic relationships from nanochannel-based optical maps, 07 2019.
  * [11] L. Mendelowitz and M. Pop.  Computational methods for optical mapping.  Gigascience, 3(1):33, 2014.
  * [12] L. M. Mendelowitz, D. C. Schwartz, and M. Pop.  Maligner: a fast ordered restriction map aligner.  Bioinformatics, 32(7):1016–1022, 04 2016.
  * [13] M. D. Muggli, S. J. Puglisi, and C. Boucher.  Kohdista: an efficient method to index and query possible Rmap alignments.  Algorithms Mol Biol, 14:25, 2019.
  * [14] K. Mukherjee, D. Washimkar, M. D. Muggli, L. Salmela, and C. Boucher.  Error correcting optical mapping data.  Gigascience, 7(6), 06 2018.
  * [15] Nabsys.  Nabsys website.  https://nabsys.com/.  Accessed 30 Sep 2021.
  * [16] R. M. Nowak, J. P. Jastrzebski, W. Kusmirek, R. Salamatin, M. Rydzanicz, A. Sobczyk Kopciol, A. Sulima Celinska, L. Paukszto, K. G. Makowczenko, R. Ploski, V. V. Tkach, K. Basalaj, and D. Mlocicki.  Hybrid de novo whole-genome assembly and annotation of the model tapeworm Hymenolepis diminuta.  Scientific Data, 6:1 – 6, 2019.  doi:10.1038/s41597-019-0311-3.
  * [17] J. S. Oliver, A. Catalano, J. R. Davis, B. S. Grinberg, T. E. Hutchins, M. D. Kaiser, S. Nurnberg, J. M. Sage, L. Seward, G. Simelgor, et al.  High-definition electronic genome maps from single molecule data.  BioRxiv, page 139840, 2017.
  * [18] M. C. Riley, B. C. Kirkup, J. D. Johnson, E. P. Lesho, and C. F. Ockenhouse.  Rapid whole genome optical mapping of Plasmodium falciparum.  Malar J, 10:252, Aug 2011.
  * [19] L. Salmela, K. Mukherjee, S. J. Puglisi, M. D. Muggli, and C. Boucher.  Fast and accurate correction of optical mapping data via spaced seeds.  Bioinformatics, 36(3):682–689, 02 2020.
  * [20] D. C. Schwartz, X. Li, L. I. Hernandez, S. P. Ramnarain, E. J. Huff, and Y. K. Wang.  Ordered restriction maps of Saccharomyces cerevisiae chromosomes constructed by optical mapping.  Science, 262(5130):110–114, 10 1993.
  * [21] J. A. Udall and R. K. Dawe.  Is It Ordered Correctly? Validating Genome Assemblies by Optical Mapping.  Plant Cell, 30(1):7–14, 2018.
  * [22] A. Valouev, L. Li, Y. C. Liu, D. C. Schwartz, Y. Yang, Y. Zhang, and M. S. Waterman.  Alignment of optical maps.  J Comput Biol, 13(2):442–462, 3 2006.
  * [23] A. Valouev, D. C. Schwartz, S. Zhou, and M. S. Waterman.  An algorithm for assembly of ordered restriction maps from single DNA molecules.  Proc. Natl. Acad. Sci. U.S.A., 103(43):15770–15775, 10 2006.
  * [24] A. Valouev, Y. Zhang, D. C. Schwartz, and M. S. Waterman.  Refinement of optical map assemblies.  Bioinformatics, 22(10):1217–1224, 05 2006.
  * [25] C. Vranken, J. Deen, L. Dirix, T. Stakenborg, W. Dehaen, V. Leen, J. Hofkens, and R. K. Neely.  Super-resolution optical DNA Mapping via DNA methyltransferase-directed click chemistry.  Nucleic Acids Res., 42(7):e50, 4 2014.