Neighbor-wise constraint propagation in dynamic time warping
Summary
Apply neighbor-wise constraint edges during dynamic time warping alignment to enforce consistency of retention-time warping functions across adjacent LC-MS samples, improving alignment accuracy for compound-specific features that would otherwise diverge under sample-independent warping assumptions.
When to use
When XCMS or other DTW-based aligners have produced misaligned LC-MS feature groups across hundreds of samples or long acquisition periods (>1 week), particularly when individual m/z bins or compounds show inconsistent retention-time drift patterns across neighboring samples. The skill is triggered by detection of features with sufficiently small p-values under higher-resolution alignment that have disjoint sample subsets, indicating localized misalignment.
When NOT to use
- Input is a single LC-MS sample or very small cohort (<3 samples) where neighbor constraints cannot propagate meaningfully.
- XCMS alignment is already accurate and misalignment detection yields no features with sufficiently small p-values (i.e., no misalignment present).
- Input data has already been realigned by another reference-based method; neighbor-wise constraints assume reference-free pairwise structure that may conflict with fixed anchors.
Inputs
- ncGTWinputs object (loaded LC-MS profile data with XCMS-aligned features and metadata)
- xcmsSet object (XCMS alignment results including corrected retention times)
Outputs
- ncGTW warping functions (neighbor-constrained, compound-specific retention-time correction coefficients)
- Adjusted RT values (output of adjustRT() replacing xcmsLargeWin@rt$corrected for downstream peak-filling and regrouping)
How to apply
Within the ncGTWalign() function, construct constraint edges on warping functions between neighboring samples to enforce smooth, sample-adjacent consistency of compound-specific retention-time warping. The algorithm: (1) accepts loaded ncGTWinputs (XCMS-preprocessed LC-MS profiles with metadata) and an xcmsSet object; (2) performs all possible pairwise alignments between sample pairs while propagating neighbor constraints as structural information; (3) uses these pairwise alignments as constraints to estimate aggregate warping functions for each sample that satisfy neighbor-wise consistency; (4) applies configurable parallel grouping (parSamp parameter) and worker threads (bpParam parameter) to scale across large cohorts. The rationale is that individual compounds often have localized, sample-dependent RT drift structures that violate the global single-warping-function assumption of XCMS, so constraining neighbors prevents spurious divergence while allowing compound-specificity.
Related tools
- ncGTW (Primary R package implementing neighbor-wise compound-specific graphical time warping with constraint edges on neighboring samples) — https://github.com/ChiungTingWu/ncGTW
- xcms (Upstream LC-MS feature detection and global alignment whose misaligned features ncGTW detects and realigns)
- graphical time warping (GTW) (Parent algorithm improved by ncGTW to incorporate neighbor-wise constraints and compound-specificity)
- dynamic time warping (DTW) (Core distance metric underlying GTW and ncGTW pairwise alignment)
Examples
ncGTWalign(object = xcmsSet_obj, input = ncGTWinputs_obj, parSamp = 10, bpParam = BiocParallel::bplapply); adjustRT(ncGTWalign_output)
Evaluation signals
- Neighbor-constrained warping functions should show smooth, continuous drift across adjacent samples for the same compound (no sharp discontinuities in RT correction between samples i and i+1).
- p-values for realigned features should be elevated (weaker significance of misalignment) compared to pre-realignment p-values, indicating correction has reduced spurious separation.
- Downstream XCMS peak-regrouping and peak-filling operations should converge to fewer, larger feature groups with consistent m/z and RT ranges across samples.
- Compound-specific warping functions should vary between different m/z bins, confirming that the method does not revert to a single global warping function.
- Pairwise alignment consistency: constraint-satisfaction check that each sample's warping function to the common coordinate satisfies edges to neighbors within a specified tolerance.
Limitations
- Misalignment detection relies on p-value significance under higher-resolution alignment; features with low signal-to-noise ratio may not generate reliable p-values.
- Neighbor-wise constraints assume spatial proximity in sample order (e.g., temporal or batch adjacency); if samples are randomly ordered or from disparate acquisition blocks, constraint edges may not encode meaningful structure.
- Reference-free, all-pairwise-alignment approach scales quadratically with sample count; for >1000 samples, computational cost and memory may become prohibitive unless parallelization is tuned.
- The algorithm requires that XCMS has already been run; it cannot recover from XCMS parameter misconfiguration if the entire feature set is misaligned uniformly rather than in localized subsets.
Evidence
- [intro] ncGTW uses individualized warping functions for different compounds and assigns constraint edges on warping functions of neighboring samples: "ncGTW uses individualized warping functions for different compounds and assigns constraint edges on warping functions of neighboring samples."
- [other] ncGTWalign() accepts loaded profile data and xcmsSet, applies alignment with configurable parallel sample grouping and workers: "ncGTWalign() accepts loaded profile data (ncGTWinputs) and an xcmsSet object, applies alignment with configurable parallel sample grouping (parSamp parameter) and workers (bpParam parameter)"
- [other] adjustRT() generates new RT warping functions that replace XCMS-derived corrections for downstream peak-filling: "adjustRT() generates new RT warping functions that replace xcmsLargeWin@rt$corrected for downstream peak-filling and regrouping."
- [readme] ncGTW detects misalignment via p-value and disjoint sample subsets, then realigns using pairwise alignments as constraints: "ncGTW algorithm estimates the p-value of each feature using higher resolution alignment result, where the p-value is given by the null hypothesis with accurate alignment. Second, we identifies all"
- [readme] ncGTW performs all possible pairwise alignments with structure information, then estimates warping functions for all samples to a coordinate: "ncGTW performs all possible pairwise alignments between each two sample with the structure information in the dataset. Second, with all the pairwise alignment as constraints, ncGTW estimates the"
- [intro] XCMS assumes all m/z bins in the same sample share one warping function, which fails with hundreds of samples or week-long acquisition: "ncGTW can detect misaligned features produced by xcms due to the assumption that all m/z bins in the same sample share the same warping function, which often fails with hundreds of samples or data"
1---2name: neighbor-wise-constraint-propagation-in-dtw3description: Use when when XCMS or other DTW-based aligners have produced misaligned LC-MS feature groups across hundreds of samples or long acquisition periods (>1 week), particularly when individual m/z bins or compounds show inconsistent retention-time drift patterns across neighboring samples.4license: CC-BY-4.05---67# Neighbor-wise constraint propagation in dynamic time warping89## Summary1011Apply neighbor-wise constraint edges during dynamic time warping alignment to enforce consistency of retention-time warping functions across adjacent LC-MS samples, improving alignment accuracy for compound-specific features that would otherwise diverge under sample-independent warping assumptions.1213## When to use1415When XCMS or other DTW-based aligners have produced misaligned LC-MS feature groups across hundreds of samples or long acquisition periods (>1 week), particularly when individual m/z bins or compounds show inconsistent retention-time drift patterns across neighboring samples. The skill is triggered by detection of features with sufficiently small p-values under higher-resolution alignment that have disjoint sample subsets, indicating localized misalignment.1617## When NOT to use1819- Input is a single LC-MS sample or very small cohort (<3 samples) where neighbor constraints cannot propagate meaningfully.20- XCMS alignment is already accurate and misalignment detection yields no features with sufficiently small p-values (i.e., no misalignment present).21- Input data has already been realigned by another reference-based method; neighbor-wise constraints assume reference-free pairwise structure that may conflict with fixed anchors.2223## Inputs2425- ncGTWinputs object (loaded LC-MS profile data with XCMS-aligned features and metadata)26- xcmsSet object (XCMS alignment results including corrected retention times)2728## Outputs2930- ncGTW warping functions (neighbor-constrained, compound-specific retention-time correction coefficients)31- Adjusted RT values (output of adjustRT() replacing xcmsLargeWin@rt$corrected for downstream peak-filling and regrouping)3233## How to apply3435Within the ncGTWalign() function, construct constraint edges on warping functions between neighboring samples to enforce smooth, sample-adjacent consistency of compound-specific retention-time warping. The algorithm: (1) accepts loaded ncGTWinputs (XCMS-preprocessed LC-MS profiles with metadata) and an xcmsSet object; (2) performs all possible pairwise alignments between sample pairs while propagating neighbor constraints as structural information; (3) uses these pairwise alignments as constraints to estimate aggregate warping functions for each sample that satisfy neighbor-wise consistency; (4) applies configurable parallel grouping (parSamp parameter) and worker threads (bpParam parameter) to scale across large cohorts. The rationale is that individual compounds often have localized, sample-dependent RT drift structures that violate the global single-warping-function assumption of XCMS, so constraining neighbors prevents spurious divergence while allowing compound-specificity.3637## Related tools3839- **ncGTW** (Primary R package implementing neighbor-wise compound-specific graphical time warping with constraint edges on neighboring samples) — https://github.com/ChiungTingWu/ncGTW40- **xcms** (Upstream LC-MS feature detection and global alignment whose misaligned features ncGTW detects and realigns)41- **graphical time warping (GTW)** (Parent algorithm improved by ncGTW to incorporate neighbor-wise constraints and compound-specificity)42- **dynamic time warping (DTW)** (Core distance metric underlying GTW and ncGTW pairwise alignment)4344## Examples4546```47ncGTWalign(object = xcmsSet_obj, input = ncGTWinputs_obj, parSamp = 10, bpParam = BiocParallel::bplapply); adjustRT(ncGTWalign_output)48```4950## Evaluation signals5152- Neighbor-constrained warping functions should show smooth, continuous drift across adjacent samples for the same compound (no sharp discontinuities in RT correction between samples i and i+1).53- p-values for realigned features should be elevated (weaker significance of misalignment) compared to pre-realignment p-values, indicating correction has reduced spurious separation.54- Downstream XCMS peak-regrouping and peak-filling operations should converge to fewer, larger feature groups with consistent m/z and RT ranges across samples.55- Compound-specific warping functions should vary between different m/z bins, confirming that the method does not revert to a single global warping function.56- Pairwise alignment consistency: constraint-satisfaction check that each sample's warping function to the common coordinate satisfies edges to neighbors within a specified tolerance.5758## Limitations5960- Misalignment detection relies on p-value significance under higher-resolution alignment; features with low signal-to-noise ratio may not generate reliable p-values.61- Neighbor-wise constraints assume spatial proximity in sample order (e.g., temporal or batch adjacency); if samples are randomly ordered or from disparate acquisition blocks, constraint edges may not encode meaningful structure.62- Reference-free, all-pairwise-alignment approach scales quadratically with sample count; for >1000 samples, computational cost and memory may become prohibitive unless parallelization is tuned.63- The algorithm requires that XCMS has already been run; it cannot recover from XCMS parameter misconfiguration if the entire feature set is misaligned uniformly rather than in localized subsets.6465## Evidence6667- [intro] ncGTW uses individualized warping functions for different compounds and assigns constraint edges on warping functions of neighboring samples: "ncGTW uses individualized warping functions for different compounds and assigns constraint edges on warping functions of neighboring samples."68- [other] ncGTWalign() accepts loaded profile data and xcmsSet, applies alignment with configurable parallel sample grouping and workers: "ncGTWalign() accepts loaded profile data (ncGTWinputs) and an xcmsSet object, applies alignment with configurable parallel sample grouping (parSamp parameter) and workers (bpParam parameter)"69- [other] adjustRT() generates new RT warping functions that replace XCMS-derived corrections for downstream peak-filling: "adjustRT() generates new RT warping functions that replace xcmsLargeWin@rt$corrected for downstream peak-filling and regrouping."70- [readme] ncGTW detects misalignment via p-value and disjoint sample subsets, then realigns using pairwise alignments as constraints: "ncGTW algorithm estimates the p-value of each feature using higher resolution alignment result, where the p-value is given by the null hypothesis with accurate alignment. Second, we identifies all"71- [readme] ncGTW performs all possible pairwise alignments with structure information, then estimates warping functions for all samples to a coordinate: "ncGTW performs all possible pairwise alignments between each two sample with the structure information in the dataset. Second, with all the pairwise alignment as constraints, ncGTW estimates the"72- [intro] XCMS assumes all m/z bins in the same sample share one warping function, which fails with hundreds of samples or week-long acquisition: "ncGTW can detect misaligned features produced by xcms due to the assumption that all m/z bins in the same sample share the same warping function, which often fails with hundreds of samples or data"
