Experimental data for the de novo OGM assembly.

In optical genome mapping (OGM), large numbers of individual DNA maps—sequence-specific data series along single DNA molecules—are produced. Such individual maps have to be stitched together in a process called de novo OGM assembly in order to create consensus OGM maps for corresponding regions along the chromosomes. While there are several types of experimental OGM assays, not all of them have de novo OGM assembly tools available. In particular, in densely-labelled OGM there are no such tools. Here, we present and evaluate DOGMA, a de novo OGM assembly algorithm for densely labelled OGM data which uses matrix profiles. Matrix profile has transformed how data mining problems are approached in time series analysis. Yet, this algorithm has not been widely explored outside of the time series community— we here use it for OGM de novo assembly for the first time. Further novelties in our algorithm are the introduction of two scores for each individual alignment, use of p-values, a visual representation as barcode islands and the introduction of a method for generating consensus barcodes using amplitude adjustment. Utilizing p-values helps mitigate the risk of errors in the assemblies as caused by false positives. We demonstrate our algorithm by applying it for de novo OGM assembly of synthetic datasets and of an experimental dataset from an Escherichia coli genome. We validate the assemblies using corresponding reference genomes and investigate the strengths and limitations of the algorithm. De novo OGM assembly of dense optical DNA maps shows promise as a complement or an alternative to current OGM techniques for other types of genome mapping assays. The code is available at: https://github.com/dnadevcode/dogma.光学基因组图谱（optical genome mapping, OGM）技术可产生大量单条DNA分子上的序列特异性数据序列，即单条DNA图谱。此类单条DNA图谱需通过名为从头光学基因组图谱组装（de novo OGM assembly）的流程进行拼接，以生成对应染色体区域的一致性光学基因组图谱。尽管目前存在多种实验型OGM检测技术，但并非所有技术都配有适配的从头OGM组装工具，尤其是在高密度标记OGM领域，目前尚无此类工具。本文提出并评估了DOGMA——一款针对高密度标记OGM数据、基于矩阵轮廓（matrix profile）的从头OGM组装算法。矩阵轮廓已革新了时间序列分析中的数据挖掘问题求解方式，但该方法在时间序列领域之外尚未得到广泛探索——本文首次将其应用于OGM从头组装任务。本算法的额外创新点包括：为每条单独比对引入两项评分指标、采用p值、以条形码岛（barcode islands）作为可视化形式，以及提出一种基于振幅调整生成一致性条形码的方法。借助p值可有效降低由假阳性导致的组装错误风险。我们通过将DOGMA应用于合成数据集以及大肠杆菌（Escherichia coli）基因组的实验数据集的从头OGM组装，验证了该算法的有效性。我们通过匹配参考基因组对组装结果进行验证，并分析了该算法的优势与局限性。高密度光学DNA图谱的从头OGM组装技术，有望作为现有其他类型基因组图谱检测技术的补充或替代方案。相关代码已开源至：https://github.com/dnadevcode/dogma.