with the emergence of liquid chromatography coupled to mass spectrometry ( lc - ms ) as a predominant method for bioanalysis , a number of software packages have been tailored for the alignment of data sets from multiple lc - ms analyses . in particular these and related algorithms
have targeted comparative metabolomic and proteomics applications and have been widely demonstrated to provide an improved level of comparison for complex samples .  
several of these methods have been recently reviewed by katajamaa and oresic , vandenbogaert et al . , america and cordewener , and lange et al . .  
there are methods which identify and select significant features from the raw data that are used as a reference for alignment ; here we refer to these as feature - based methods .
alternatively , there are those that use the whole data , which we refer to as profile - based methods .  
the data points from lc - ms analyses can be defined by their mass - to - charge ratios ( m / z ) , retention times , and intensities .
this combination of numeric attributes is often referred to as a feature vector and when one of these attributes ( usually intensity ) is expressed by color scale , these features can be conveniently visualized as a plot , sometimes described as an lc - ms contour map or lc - ms image . in the feature - based alignment method of wang et al .
, the concept of an element spectrum vector was defined as the peak pattern of a specific peptide in an otherwise empty mass spectrum .
these vectors can then be created for each possible peptide and used to align the experimental mass spectra .   with the profile - based methods , in which alignment
is performed prior to feature extraction , the likelihood of errors due to feature detection is reduced .
the earliest of these methods used the total ion chromatogram ( tic ) approach in which the sum of peak intensities of each spectrum is used as the basis of alignment ; the more similar the sum is in two spectra from different samples , the more likely it is that they will match [ 7 , 8 ] .
an example of such a method is the tic - based system of listgarten et al .   , which was later enhanced by dividing the spectrum into four bins , with each bin containing about the same amount of ion current .
a hidden markov model was used to represent the true retention times of the spectra , the parameters of which were estimated using the maximum likelihood principle and the expectation maximization algorithm .
krebs et al .   presented an alignment method for gas chromatography - ms data which used splines and hermite functions to correct the retention times .
retention time errors were estimated from automatically selected landmarks that the software determined from correlation of the tic - peaks .
presented a similarity score for each spectrum pair , which was calculated on the basis of the presence of similar peaks in the same mass position and by taking into account their neighbourhoods and the possibility of a random match .
jaitly et al .   presented the lcmswarp method for the alignment of lc - ms data sets .
they argue that some of the differences in retention time are global and linear and are corrected more easily .
the data sets are divided into sections , and the alignment of the different sections are scored using a similarity score , which is based on the mahalanobis distances calculated from the matches between sections .   in applications of alignment methods for comparison of multiple analyses , errors in mass axis
are generally small , but differences in the time axis and column replacement may be sufficient to introduce ambiguity in peak matching .
furthermore , with a complete lc - ms sample series , the variations encountered in retention times may be larger than anticipated and at times nonlinear .
fluctuations in temperature , mobile phase flow rate and composition , as well as the accumulation of contaminants in the column and minor changes in sample composition among other inconsistencies in running conditions will account for deviations in retention times between the runs . in situations of high sample complexity and varied separation reproducibility , the alignment of several lc - ms images is not a trivial task . in effect , a computer algorithm is needed to address two important tasks : recognize the features arising from the same set of analytes between different runs and transform the retention times of features of different runs so that they become identical and comparable . with proteomics , this translates into the comparison of profiles of thousands of peptides which are often closely eluting in time , within a narrow mass to charge window .
moreover , with experiments involving several case / control groups and multiple time points , where the sample numbers can extend from tens to hundreds , the researcher should be able to reliably compare a very large number of peaks and determine statistically significant differences within the dataset .   in our applied research towards the identification of protein biomarkers for type 1 diabetes
we have investigated the longitudinal proteomic profiles of serum from subjects with a hla class ii haplotype defined risk of type-1 diabetes .
part of this strategy has been based on the use of a label free lc - matrix assisted laser desorption ionization ( lc - maldi ) approach [ 1315 ] .
the lc - maldi method enables the storage of separated peptides on the maldi target plate .
data are created from a maldi analysis of the material collected on the target , providing a list of singly charged peptide ions identified in this primary analysis . following an intra - run based global normalization the peptide lists
are compared between different samples and differences and/or interesting peaks further determined by further analysis ( ms / ms ) of the maldi target plate . to maximize the descriptive potential of this data set and accommodate for deviations and technical variations , an alignment step was introduced during the primary comparison phase .
our initial data evaluation began with mzmine ( version 0.6 ) , but to add additional flexibility to the alignment , a new alignment tool was developed . in the present paper , we describe a versatile easy to use lc - ms data alignment package ( polyalign ) with options for both automated and user selected landmark - based alignment .
the output of the tool is a set of lc - ms images where the retention times are corrected according to the alignment between the images .
the tool was implemented both as a stand - alone package and an addition to mzmine .
a profile - based lc - ms data alignment approach is used that is based on a global transformation method for retention time correction , with either a polynomial or hermite based model .
importantly , in the design of the alignment package we gave strong emphasis for the ease of use and installation of the alignment tool .
here we aimed at simple and effective controls and an intuitive direct visual control of the warping phase through a convenient gui . with
the material tested the use of the hermite interpolation indicated superiority in its speed and efficacy in the alignment .
the implementation was designed to be versatile towards data produced by different types of mass spectrometers in mzxml format , including lc - maldi and lc - esi configurations .
for the evaluation and testing of the proposed alignment software , we have used both lc - maldi and lc - esi data .
the lc - maldi data were from the analyses of serum samples periodically collected from case and control subjects , as a part of the finnish nationwide diabetes prevention and prediction study ( dippstudy , ) .
aliquots of the serum ( 8  l ) were depleted of the 6 most abundant serum proteins with an agilent  mars  serum depletion spin column .
samples were reduced , alkylated , and then digested with trypsin ( promega , sequence grade ) .
the serum digests were separated with an 100  um  75  um i.d . 
peptide separation was performed using a gradient from 530% b in 120  min at a mobile phase flow rate of 255  nl / min .
the phase compositions was as follows : phase a. 5% acetonitrile , 0.1% trifluoroacetic acid ; phase b , 95% acetonitrile , 0.1% trifluoroacetic acid .
the column eluate was collected directly to polymeric anchor chip ( pac ) maldi target plates ( bruker daltonics ) , using a probot ( lcpackings ) spotting robot , at 128 discrete loci from 21.5 minutes to 97.2 minutes , with spotting intervals of 35 seconds .
an ultraflex ii tof / tof maldi mass spectrometer ( bruker daltonics ) was used in reflector mode with a m / z range from 7503500  da . for each sample matrix spot
the separations were performed at a temperature of 55c , which provided both an improved   separation efficiency ( due to increased mass transfer in the mobile phase ) and a reduced operating pressure ( due to decreased mobile phase viscosity ) .
the combination of an elevated separation temperature facilitated the use of an un - modified nano - lc instrument with uplc media .     for lc - esi test material , serum samples were depleted of the top 6 most abundant serum proteins and prepared for lc - ms analysis as described for the lc - maldi samples .
aliquots ( ~0.5  g ) of the serum digests were analyzed by lc - ms / ms using a system consisting of lc - packings ultimate - ii nanoflow - lc ( lc packings , amsterdam , netherlands ) coupled to a qstar pulsar esi - hybrid quadrupole - time of flight instrument ( applied biosystems / mds sciex ) .
fused silica capillary column packed with 5  m magic c18   ( michrom bioresources , inc . , auburn , ca ) .
peptide separation was performed using a gradient from 235% b in 124  min at a mobile phase flow rate of 200  nl / min .
the phase compositions were as follows : phase a. 5% acn , 0.1% hcooh ; phase b , 95% acn , 0.1% hcooh .
data analysis was performed with mascot ( version 2.2 , matrix science , london , uk ) , and the data were searched against a swissprot database ( release date 05/12/2005 ) with mammalian specific taxonomy .
methionine oxidation was specified as variable modification , and carboamido methylation modification of cysteine as a fixed modification .
data set 1 included 4 technical replicate analyses of a single serum sample ( dataset 1 ) , which was used to study the real technical distortion resulting from the lc - ms process without random or sample to sample error sources .
datasets 2 and 3 represent longitudinal serum samples from two subjects , with seven and five time points from subjects a and b , respectively .
samples are collected more frequently from the subjects once they are tid autoantibody positive .  
analysis of control sera was also made using esi - ms ( dataset 4 ) .
these data sets were used to test the performance of our method in a practical research setting .
artificially distorted maps   were also used in preliminary testing , the results for which are shown in the supporting information .
data files were converted to mzxml format using compassxport 1.3.1 ( bruker ) and mzstar for the bruker maldi and applied biosystems electrospray data , respectively .
the first correcting function is a polynomial function f ( called the warping polynomial ) of order k :  
 ( 1)f(t)=i=0kciti , 
							 where t is the observed retention time and the function f(t ) gives the corrected retention time for t. the coefficients ci are determined by the least squares method   using the time differences of the set of landmarks as defined by the user or given by the automatic landmarking method .
transformation f(t ) is only done in the rt dimension due to the assumption that the mass values measured by the mass spectrometer are relatively accurate .
after manually or automatically selecting the landmarks , the regression function is estimated and the software will warp the distorted signal map .  
alternatively , the transformation can be made using a cubic hermite spline transformation , for which the transformation brings the landmarks into exact alignment , whereas in the polynomial correction this is not the case [ 20 , 21 ] .
the cubic hermite spline is a third degree spline function , with hermite polynomials used for interpolation .
the hermite polynomial for points x in the interval ( xk , xk+1 ) is 
 ( 2)p(x)=h00(t)p0+h10(t)hm0+h01(t)p1+h11(t)hm1 , 
							 where p0 and p1 are the starting and ending points , respectively , m0 and m1 starting and ending tangents , respectively , and h = xk+1  xk , and t = ( x  xk)/h .  
furthermore ,  
 ( 3)h00(t)=2t33t2 + 1 ,  h10(t)=t32t2+t ,  h01(t)=2t33t2 ,  h11(t)=t3t2 . 
							 in the tests in section 3 , manual landmark finding was used , unless stated otherwise .
a true peptide signal represents typical chromatographic elution so that the signal spans over approximately 1090 seconds with first rising and then declining intensity .
the visual control of the landmark selection allows effective recognition of true peptide signals from background peaks or electric noise .  
the landmarks should be selected relatively uniformly over the signal map , for example , representing large rt and m / z range , to guarantee that the transformation works well between the reference and object images . in theory
, the number of landmarks should be at least k + 1 for a polynomial transformation of degree k , but the general rule is that 1020 landmarks produce the best result as can be seen from figure 2 .
we studied the impact of the number of landmarks on the alignment efficiency ( see section 3 below ) and found that in practice 12 landmarks were sufficient .
a higher degree polynomial fits the landmark points better but becomes often unstable in areas with no landmarks .
a lower - order polynomial has a smoother form , but it may not catch highly nonlinear or local distortions as effectively .
we have included an option for automatic determination of the best degree of the polynomial .
the algorithm tests different degrees and    calculates a correlation coefficient for the images for each degree .
. the reference map should be the map with the most features , as this will likely make it easier to find the landmarks from other maps .
the automated landmarking algorithm is initiated with the selection of the area of the reference image from which the landmarks will be determined . by default
the whole image is used , although the user can limit the area by zooming into a part of the map .
next , the area is divided into n equal - sized parts ( i.e. , time slices ) in the retention time dimension , by default n = 20 . the most intense point in each slice
the corresponding landmarks in the other images are searched by first selecting the expected area of the landmark with a user given ms equipment - dependent tolerance in both retention time and m / z dimensions .
the maximization of the pearson correlation coefficient is then used to find the exact retention time of corresponding landmark spot inside this area .
if the correlation test does not provide a good enough value of the correlation coefficient for the landmark pair , the landmark is discarded for this image pair .
the user has then an option to inspect the results and , if wanted , remove or change landmark pairs which look suspicious , or he can add more landmark pairs . with the integration of this preprocessing tool into mzmine for the correction of distorted data , we have improved the automatic alignment phase , whilst giving the user more control over the alignment process .
the user can select landmarks by clicking the potential landmark spots at the two signal maps to be aligned .
the graphical user interface ( gui ) of the polyalign system has been designed to support the setting of landmarks in manual mode by allowing the user to insert and delete landmarks in a quick and intuitive way .  
the gui also shows the aligned map of the reference image and target image stacked together .
this enables the user to keep track of the current state of the alignment , so that he can stop inserting landmarks when the transformation is accurate enough .
although the manual landmarking requires additional user input , it also allows good visual control over the warping process .  
the process of manually setting the landmarks is greatly aided by the use of efficient zooming techniques . with the comparison of large lc - ms datasets
, the speed of image generation and zooming can be limited . as these latter attributes were a crucial requirement in the usability of our software , we applied the quadtree data structure   in order to implement fast zooming capabilities in our program .
the quadtree is based on a recursive decomposition of the data , and it thus enables the user to focus quickly on subsets ( i.e. , regions ) of the data .   
larger sets of signal maps can be aligned by repeating the pairwise alignment procedure with more data files . to assist with this , the landmarks can be saved and used with successive data files .
the user can choose one signal map as the reference map to which all the other maps are aligned .
in this way , one can process a large experiment with tens of samples simultaneously , and every single data set can then be compared against each other without the need for further alignment .  
the polyalign software has been implemented in two forms : as a simpler stand - alone perl - language preprocessor , which is capable of reading mzxml - files , processing them with an easy - to - use gui and then saving them with altered retention time values for the scans .
alternatively , the algorithm has been integrated in the popular open source software package mzmine   with all the features described above .
mzmine has advanced capabilities for identifying the peak complexes from several lc - ms images and for matching them across samples .
the integration of our algorithm into mzmine complements its original automatic alignment method [ 3 , 16 ] , with the provision of a powerful preprocessing tool for correcting distorted data sets , whilst providing the user with more control over the alignment process .
the transformed files may be processed in parallel to create peak lists for analysis with such inbuilt tools as curvilinear distance analysis ( cda ) and sammon 's nonlinear mapping ( nlm ) .
the aligned mzxml files can be exported as new mzxml files for further processing using other software .
both versions of the software are freely available from the web address http://staff.cs.utu.fi/staff/jussi.salmi/supporting.html .   several different test settings were used to evaluate the correction performance of polyalign .
firstly , we selected manually a large number of landmarks and divided them into testing and training sets , and used r - fold cross - validation for estimating the warping error .
in particular , the landmark set was divided into r , groups , and then one group was used for estimating the alignment function and the error of the alignment was calculated using the other groups . by varying r we could find the optimal amount of landmarks for training : we observed that as more landmarks were added in the training set , the training set error increased and the testing set error typically decreased .
initially we observed that the training error was smaller than the testing error and finally reached a point at which the addition of more landmarks did not improve the alignment . a root mean square error , rms , measure was used for these tests , defined as 
 ( 4)rms=1|m|(,t)m(t)2 , 
							 where m is the set of landmarks used as the testing set , and it consists of pairs (  , t ) , where  is the retention time of the landmark in the reference map and t the retention time of the landmark in the distorted map .
the rms values are both before and after the alignment of the lc - ms images .
these results confirm the above findings , and they are available in the supporting information .
we have developed a profile - based lc - ms alignment tool for the analysis of multiple data files on the basis of polynomial and hermite transformation . with the practical testing of this software
, we needed to establish whether the method improved the alignment of the data , whilst establishing the optimal degree for the warping polynomial and the number of landmarks required for a good alignment .
while the tests with the polynomial transformation were performed with polynomial degrees 13 , only the results obtained with the best degree are shown here .
complete tables for these with all the polynomial degrees are shown in the supporting material .
for the technical replicates ( data set 1 ) , the root mean square errors are given in table 2 .
in general , the error decreased as a result of warping by polyalign , but for the target map 1 it increased . after studying map 1 further
, it was found that with this analysis a more intense background was observed across much of the chromatogram , with several broad tailing features that were not in the reference map , and thus it did not correlate well with the reference data set .
tables 3 and 4 summarize the results for aligning the signal maps of subjects a and b ( data sets 2 and 3 ) , respectively . again , the landmark error decreased systematically in each case as a result of the alignment .
some of the maps proved difficult to align due to the scarcity of good landmarks in some areas of the maps , and in part reflecting some of the limitations of the lc - maldi strategy .
the wilcoxon signed rank test was used to test the statistical significance of the test results . in both cases , the alignment proved to improve significantly ( p < .05 ) as a result of the alignment . on the basis of the experiments above ,
we conclude that there is no specific degree for the warping polynomial that should be favoured in general .
if the data has a simple shift in starting time , then the linear correction works well enough , and the unnecessary complications of the higher degree coefficients can be avoided , as can be seen with the artificially distorted test material in the supporting material . however , in the test material sets 2 and 3 , 2nd or 3rd degree terms are needed to model the distortion in many cases .
in particular , it is advised that the user may choose between different degrees for the polynomial to get the best possible warping performance .   for the evaluation of landmark setting
, we found that 12 landmark pairs appeared to be sufficient for our test material .
figure 2 shows a representative plot of the average correction error as a function of the number of landmark pairs .
similar figures for the other cases of the data set are shown in the supporting material .
the test and training set errors converge after 12 landmarks . with these lc - maldi data ,
the number of mass spectra per analysis was determined by the number of maldi spots collected , that is , just 128 .   with esi - lc - ms data , however , the number of mass spectra is far greater , as the data are acquired with 20 or more full ms1 scans per minute .
peak matching between data sets was tested using both lc - esi and lc - maldi data .
here we calculated the number of peak groups that could be matched between the maps of the test data set .
the maps were aligned with the mzmine embedded version of the polyalign and the original mzmine alignment method using a retention time tolerance of 105 seconds .  
figure 3 shows the number of peak groups that were matched between the different maps . in general , with a successful alignment technique
, a large number of matching peaks would be expected from all the 8 maps . on the contrary to this , if most of the matches only occur between a few maps , the alignment may be less successful
. the results of figure 3 show that the number of peak matches clearly improved compared to the original mzmine algorithm .
the hermite transformation was the most successful method with this material , as shown by the distribution of the sizes of matching peak groups .
polynomial methods with different degrees k and the automatic landmarking system without any correction to landmark positions were also better than the original mzmine .
we believe that the hermite transformation demonstrated a superior performance in this application as it follows the landmarks exactly , whereas the polynomial method accepts a transformation function which does not go via the landmark points .
figure 4 shows the corresponding results for 6 maps from the lc - esi data set with 1% rt tolerance in matching the peaks .
again the hermite interpolation with manual landmarking was the most successful method , but very good results were also achieved using the automatic landmarking system .  
figure 5 shows an example of a successful alignment with two lc - maldi maps .
in the critical review of alignment methods by lange et al .   several different software packages were compared .
these included mzmine , openms , xalign , xcms , specarray , and msinspect , with the first three performing about equally well .
our algorithm can be used as stand - alone method to produce a set of mzxml - files for further analysis or as an enhancement of mzmine .
the proposed algorithm provides an improvement over mzmine as was demonstrated in this section , so we believe that our method would be a useful tool for lc - ms alignment .
unfortunately , we were unable to use the dataset of lange et al . for testing , as their alignment comparisons were made using a preprocessing step for feature detection , creating featurexml files .  
in contrast , our program was developed to directly align mzxml files and requires the full mass versus time spectral profiles that are absent from featurexml formatted data .
lc - ms profiling has a great potential in comparative proteomics [ 26 , 27 ] .
furthermore , the production of detailed and accountable ms profiles can be highly beneficial for biomarker discovery experiments   and label - free comparative quantitative proteomics .
the alignment of lc - ms profiles from separate measurements is an important prerequisite for such applications as it can improve data comparison and extend the depth of analysis .
although several algorithms for lc - ms data alignment are now both commercially   and freely [ 31 , 32 ] available , in our application we aimed to provide an additional level of flexibility that would facilitate the comparison of analyses across a prolonged study whilst putting emphasis on the ease of use and user control .
although the landmark selection requires an additional level of user input , it also provides a very good visual control   over the data quality .
the user has full power over the alignment process , and can see the changes in the combined image pair as more landmarks are inserted and the transformation model is developed . in this phase , the user can quickly evaluate whether the data set is compromised with the insertion of erroneous landmarks , thus providing an additional level of confidence . for aiding the user
the option includes also the possibility for easily editing the landmarks proposed by the module .
our mzxml format - based data alignment module polyalign was developed for use with both lc - maldi and electrospray data .
we have created a flexible and efficient lc - ms profile alignment tool that stands out due to its real life usability .
it can be operated with layman windows user knowledge , thus saving time and effort in the early stage of ms - profiling data interpretation .
this software is freely available as a stand - alone perl - language preprocessor and as an addition to the mzmine toolbox
. both versions of the software are available together with examples of the esi and maldi data from the web address http://staff.cs.utu.fi/staff/jussi.salmi/supporting.html .
 we present a versatile user - friendly software tool , polyalign , for the alignment of multiple lc - ms signal maps with the option of manual landmark setting or automated alignment . 
 one of the spectral images is selected as a reference map , and after manually setting the landmarks , the program warps the images using either polynomial or hermite transformation . 
 the software provides an option for automated landmark finding . 
 the software includes a very fast zoom - in function synchronized between the images , which facilitate detecting correspondences between the adjacent images . 
 such an interactive visual process enables the analyst to decide when the alignment is satisfactory and to correct known irregularities . 
 we demonstrate that the software provides significant improvements in the alignment of lc - maldi data , with 1015 landmark pairs , and it is also applicable to correcting electrospray lc - ms data . 
 the results with practical data show substantial improvement in peak alignment compared to mzmine , which was among the best analysis packages in a recent assessment . 
 the polyalign software is freely available and easily accessible as an integrated component of the popular mzmine software , and also as a simpler stand - alone perl implementation to preview data and apply landmark directed polynomial transformation . 
1. Introduction
2. Experimental Section
3. Results and Discussion
4. Conclusions