Graph-based time alignment algorithms for LC-MS datasets with large retention-time drifts

Liquid chromatography coupled to mass spectrometry (LC-MS) is the dominant technological platform for proteomics. An LC-MS analysis of a complex biological sample can be visualized as a “map” of which the positional coordinates are the mass-to-charge ratio (m/z) and chromatographic retention time (RT) of the chemical species profiled. Label-free quantitative proteomics requires the alignment and comparison of multiple LC-MS maps to ascertain the reproducibility of experiments or reveal proteome changes under different conditions. The main challenge in this task lies in correcting retention time shifts, which are inevitable even on the same instrument and under the same elution conditions. For large-scale studies, multiple instruments or multi-week experiments are often required, which exacerbates the problem. Similar, but not identical, LC instruments and settings can cause peptides to elute in a different order, violating the key assumption of many state-of-the-art alignment tools. We present a new graph-based time alignment algorithm that can align these less similar LC-MS maps, which cannot be effectively handled by existing methods. We developed WBMatch, which is based on an efficient weighted bipartite matching algorithm from graph theory, to align different LC-MS maps. Instead of finding warping functions to correct the variations in the retention time dimension, WBMatch directly tries to find a peak-to-peak mapping that maximize a similarity function between two LC-MS maps. The similarity function is a combination of m/z, retention time and intensity deviations of all aligned peaks. In order to handle large retention time shifts between LC-MS experiments conducted from different instruments or settings, an additional step of locally weighted scatterplot smoothing is performed prior to WBMatch, forming a new method called LWBMatch. For validation, we defined the ground-truth for alignment success based on MS/MS identifications from sequence searching. We showed that our method outperforms several existing tools in terms of precision and recall, and is capable of aligning maps from different instruments and settings