SynchDP: A correlation based sequence alignment algorithm for synchronizing longitudinal clinical data

Analogous to the sequence-to-sequence alignment problem in discrete settings, two time-series can be aligned based on their longitudinal similarity. In disease contexts, aligning time-series that represent patient severity levels allows quantifying the similarity in their progression. However, in real-world clinical settings, patients are hospitalized at varying stages, and measurements are taken at irregular intervals, leading to sequences of different lengths and sampling rates. This complicates direct comparison of gene expression profiles and hinders biomarker discovery. Here, we propose a correlation based dynamic programming algorithm, SynchDP, that aligns and synchronizes two or more clinical time-series sequences with irregular and asynchronous properties. It is also able to assemble representative patterns from the input sequences de novo.

Synthetic sequences with gaps and shifts were generated to show that SynchDP successfully aligned them with significantly higher quality than competitive methods. Longitudinal severity levels of COVID-19 patients were aligned and synchronized using SynchDP to identify patients with deteriorating or recovering health conditions. For biological validation, based on the alignment results, genes associated to the two conditions were searched in patient-matched single-cell transcriptome samples and showed that severity progression-related biomarkers were well captured.

https://github.com/cobi-git/SynchDP.