An accurate and rapid continuous wavelet dynamic time warping algorithm for end-to-end mapping in ultra-long nanopore...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Nanopore sequencing offers long-read, point-of-care, and polymerase chain reaction-free capabilities.
• Accurate signal mapping is crucial for downstream nanopore data analysis, including signal labeling, visualization, variant identification, and methylation detection.
• Classical dynamic time warping (DTW) is computationally infeasible for ultra-long nanopore sequences due to their length and sampling speed differences.

Purpose of the Study:

• To develop a novel algorithm for efficient and accurate signal mapping in nanopore sequencing data.
• To address the limitations of classical DTW for ultra-long nanopore sequences.

Main Methods:

• Proposed a multi-level dynamic time warping algorithm, continuous wavelet DTW (cwDTW).
• Utilized continuous wavelet transforms at different scales to shorten and normalize signal sequences.
• Extracted feature sequences from transformed data for efficient mapping using original DTW, followed by recursive projection of the warping path.

Main Results:

• cwDTW demonstrated significant acceleration (approximately 3000x faster than original DTW) with minimal loss in alignment accuracy.
• The algorithm successfully mapped ultra-long nanopore sequencing signals in seconds.
• Validated cwDTW's effectiveness on human and Pandoraea pnomenusa nanopore datasets for signal labeling and sequence comparison.

Conclusions:

• cwDTW is an efficient and effective algorithm for signal mapping in nanopore sequencing.
• The algorithm overcomes the computational challenges posed by ultra-long sequences and high sampling rates.
• cwDTW shows broad applicability in various nanopore data analysis tasks, enhancing the utility of long-read sequencing.