BACKGROUND
tandem mass spectrometry  has become an important method for characterizing complex protein mixtures.
since the emergence of this high-throughput technology, two complementary data analysis approaches have been pursued: a database searching approach and a de novo sequencing approach.
the former identifies peptide sequences from a protein database by matching their predicted tandem mass spectra to measured tandem mass spectra; whereas the latter infers partial or complete peptide sequences directly from measured tandem mass spectra.
due to its high identification accuracy and the rapid expansion of genomic sequence data, the database searching approach, enabled by popular algorithms such as sequest  <cit>  and mascot  <cit> , is routinely used in current proteomics workflows.
in contrast, although many de novo algorithms have been developed  <cit> , they have not been widely used in high-throughput proteomics workflows.
a high-throughput de novo sequencing capability is critically needed for detection of post-translational modifications , characterization of amino acid polymorphisms, and identification of proteins not represented in sequence databases.
de novo sequencing has been actively pursued using ms/ms data acquired with ion trap instruments, which are the workhorses of many proteomics workflows.
however, the relatively poor mass resolution, mass accuracy, and signal-to-noise ratio of ion trap ms/ms data is a large challenge for de novo sequencing.
the basic idea of de novo sequencing is that, if the mass difference between two mass spectral peaks corresponds to an amino acid mass, the two peaks are likely two adjacent fragment ions flanking a residue of the peptide.
because of the low mass accuracy of ion trap ms/ms data, it is common for two unrelated peaks to have a mass difference reasonably close to an amino acid mass by coincidence.
additionally, in ion trap tandem mass spectra, low-intensity peaks of real fragment ions are often obscured by a large number of noise peaks, again interfering with de novo sequencing.
in recent years, new hybrid mass spectrometers, such as ltq-orbitrap and ltq-ft from thermo fisher scientific inc., have become more common in proteomics workflows  <cit> .
these instruments combine the all-around ms/ms capability of ion trap with the excellent mass analysis capability of orbitrap and ft-icr.
typical proteomics measurements take high-resolution full scans with orbitrap or ft-icr and ms/ms scans with ion trap to achieve accurate parent mass analysis and fast ms/ms acquisition.
these hybrid instruments are also capable of acquiring high-resolution tandem mass spectra by performing peptide fragmentation in the front-end ion trap and then transferring fragment ions to the back-end orbitrap or ft-icr for mass analysis.
such high-resolution ms/ms data is more amenable to de novo sequencing than ms/ms data acquired on conventional ion trap instruments.
several de novo sequencing algorithms, including pepnovo  <cit> , directag  <cit> , peaks  <cit>  and msnovo  <cit> , accept both ion trap ms/ms data and high-resolution ms/ms data.
most of existing de novo sequencing algorithms can be adapted to high-resolution ms/ms data by tightening up mass error tolerance.
de novo sequencing has also been combined with a ustag approach for ptm identification using ft-orbitrap ms/ms data  <cit> .
all these algorithms should obtain a significant performance boost by using high-resolution ms/ms data.
here, we report a new de novo sequencing algorithm, vonode , to further exploit the potential of high-resolution ms/ms data by using a unique tag scoring function and a novel type of spectrum graphs.
the scoring function of vonode relies more on mass accuracy information than on ion intensity information for scoring sequence tags.
because of the improved dynamic range and sensitivity of high-resolution ms/ms data, fragment ions with lower intensity could just as likely be y and b ions as those with higher intensity.
this is contrary to the intuitive assumption that lower-intensity peaks are less significant.
a rigorous way for using intensity information is to model theoretical intensities in a spectrum for a sequence tag, which in turn requires building a reliable statistical model with comparable training data  <cit> .
in comparison, mass accuracy information in high-resolution ms/ms can be well defined statistically and is straightforward to use for scoring.
to find sequence tags, many existing de novo sequencing algorithms reconstruct spectrum graphs  <cit>  where only adjacent fragment ions of the same ion type are connected.
artifact vertices are used to represent non-existent complementary ions for lone y or b ions such that adjacent fragment ions of different ion types can be connected.
vonode uses a new type of spectrum graph where every observed product ion is transformed to one and only one vertex and four types of edges are used to represent the four possible relationships among adjacent fragment ions.
although this new type of spectrum graphs makes it algorithmically more difficulty to find sequence tags, it allows scoring of sequence tags based only on the ions observed in a mass spectrum.
vonode was compared to an established de novo sequence algorithm, pepnovo v <dig>   <cit> , to test whether these new features improves de novo sequencing.
pepnovo v <dig>  was adapted to high-resolution ms/ms data acquired on an ltq-ft instrument and its performance was shown to be significantly improved  <cit> .
this makes pepnovo v <dig>  directly comparable to vonode.
the de novo sequencing performance was benchmarked with  <dig>  high-resolution tandem mass spectra acquired from a 24-hour shotgun proteomics measurement of a bacterium rhodopseudomonas palustris.
peptide sequences were first identified for this ms/ms dataset with the sequest-dtaselect toolchain  <cit> .
to further reduce the false discovery rate of database searching, peptide identifications were filtered with parent mass accuracy using a new perl program, called sqama .
a total of  <dig>  spectra were identified with a false discovery rate of  <dig> %.
these confident peptide identifications were used to verify sequence tags generated by de novo sequencing algorithms.
from this benchmark dataset, the vonode algorithm inferred sequence tags for  <dig>  spectra at an average length of  <dig>  residues using the consensus sequence tag approach.
the accuracy of inferred consensus sequence tags was 84%.
in comparison, the pepnovo v <dig>  algorithm generated sequence tags for  <dig>  spectra with an average length of  <dig>  residues using a score cutoff of  <dig> .
the accuracy of top sequence tags from pepnovo v <dig>  was 65%.
note that vonode cannot be compared to a new version of pepnovo, pepnovo+  <cit> , for high-resolution ms/ms data, because so far pepnovo+ has only one model for low-resolution ion trap ms/ms data.
although many other de novo sequencing algorithms  <cit>  are available for additional performance benchmarking, the comparison of vonode to the established and widely-used pepnovo v. <dig>  program showed that algorithmic concepts behind vonode's scoring function and the new type of spectrum graphs are important for de novo sequencing to take full advantage of high-resolution ms/ms data.
methods
algorithm description
in an ms/ms measurement, a peptide is isolated by its m/z and fragmented with collision-induced dissociation.
the product ions are then analyzed using an ms <dig> scan.
most high-abundance product ions are y-ion type or b-ion type, generated from cleavage of peptide bonds.
b-ions are fragments on the n-terminal side and numbered as b <dig>  b <dig> and so on according to the number of residues they contain.
y-ions are fragments on the c-terminal side and similarly numbered as y <dig>  y <dig> and so on.
other product ions can form directly from the cleavage of other bonds or indirectly from secondary fragmentation  of primary product ions.
besides product ions' peaks, tandem mass spectra are also populated with noise peaks.
formally, let us define a tandem mass spectrum with a neutral parent ion mass p, a mass array {m <dig>  m <dig>  m <dig>  ..., mn in ascending order and a corresponding relative abundance array {a <dig>  a <dig>  a <dig>  ..., an.
the mass-abundance pair  has a mass of zero and a relative abundance of 100%.
all other pairs ,  <dig> ≤ i ≤ n, correspond to neutral monoisotopic masses and relative abundances of measured product ions.
mass spectral peaks are deisotoped and assigned a charge state in the pre-processing step by the vonode algorithm.
peaks that fail in deisotoping are removed.
the de novo sequencing problem is to infer partial sequences of a peptide  from its tandem mass spectrum.
a sequence tag is represented as mpr1r <dig> ..rmmq, where r1r <dig> ..rm is a sequence of amino acid residues and mp and mq are two residual masses to the two peptide termini.
a residue ri,  <dig> ≤ i ≤ m, belongs to an amino acid set a = {a, c, d, e, f, g, h, k, m, n, p, q, r, s, t, v, w, j, y}.
let m be the mass for the amino acid Ω, Ω ∈ a. note that two isobaric amino acids, i and l, are represented with one letter, j, such that every amino acid in set a has a unique mass.
sequence tags are bidirectional in that mpr1r <dig> ..rmmq is equivalent to mqrmrm- <dig> ..r1mp.
a sequence tag for a tandem mass spectrum is considered correct, if the sequence tag, in either direction, matches exactly a portion of the peptide sequence.
given multiple sequence tags inferred for a tandem mass spectrum, a longer sequence tag is more informative and, at the same time, more likely to be incorrect as the result of incorporation of a residue with wrong amino acid assignment.
generally, de novo sequencing algorithms attempts to find the longest sequence tag that is correct for a certain probability.
the vonode algorithm finds optimum sequence tags in four steps:  spectrum graph construction,  sequence graph construction,  sequence tag searching, and  sequence tag scoring.
step 1: spectrum graph construction
a spectrum graph is constructed from a tandem mass spectrum, given the amino acid set a. a vertex in the spectrum graph, vi, represents a product ion ,  <dig> ≤ i ≤ n. four types of edges are constructed in a spectrum graph, namely arrow edges, forward-slash edges, backslash edges, and vertical-bar edges.
figure  <dig> illustrates how edges in the spectrum graph are expected to connect y ions and b ions with one another.
let Ω be an amino acid  at the kth residue in a peptide of length  residues.
this residue is flanked by four product ions, yh, yh+ <dig>  bk- <dig>  and bk.
an arrow edge  is expected to connect a y ion  to the next y ion  or a b ion  to the next b ion .
a forward-slash edge  is expected to connect a y ion  with the next complementary b ion .
a backslash edge  is expected to connect a y ion  with the previous complementary b ion .
a vertical-bar edge  is expected to connect two complementary y and b ions .
given a set of vertices with unknown identity in a spectrum graph, edges are constructed between two vertices using their masses.
let ε be the relative mass error for an edge, which is the difference between the measured mass combination of two vertices and the expected mass combination given amino acid masses ) and the parent mass .
let Δ be the relative mass error tolerance .
two vertices, vi and vj, with respective masses of mi and mj,  <dig> ≤ i < j ≤ n and mi < mj, are connected by:  an arrow edge, if |  - m | = ε < Δ;  a vertical-bar edge, if |  - p | = ε < Δ;  a forward-slash edge, if | p -  - m | = ε < Δ; and  a backslash edge, if |  - p - m | = ε < Δ. the relative mass errors of spectrum edges are generally smaller than the mass errors of ions, because ion in a spectrum usually have mass errors in the same direction from out of mass calibration and the mass errors can cancel part of each other out in the relative mass error calculation.
figure  <dig> shows the spectrum graph constructed from a tandem mass spectrum of + <dig> peptide k.yrppaesaasgitvr.n.
the y and b ions of this peptide could provide information for a sequence tag of saasgjt.
two vertices that represent two adjacent y or b ions measured with sufficient mass accuracy should be connected by an edge of appropriate type.
however, two vertices that are not related can also be connected from coincidence of their mass combination.
every edge is associated with a relative mass error ε and an edge type.
step 2: sequence graph construction
a sequence graph is constructed from a spectrum graph to facilitate sequence tag searching.
for clarity, vertices and edges in a sequence graph are referred to as sequence vertices and sequence edges respectively, whereas vertices and edges in a spectrum graph are referred to as spectrum vertices and spectrum edges respectively.
a sequence vertex, representing an amino acid residue, is constructed from interconnected spectrum vertices that correspond to product ions on the two sides of the residue.
these spectrum vertices should be interconnected by spectrum edges all labeled with this residue or vertical-bar spectrum edges.
in figure  <dig>  sequence vertex Ω is constructed from spectrum vertices yh+ <dig>  yh, bk- <dig>  and bk and sequence vertex Ψ is constructed from spectrum vertices yh- <dig>  yh, bk+ <dig>  and bk.
note that a spectrum vertex can be used for multiple sequence vertices.
a sequence vertex for a residue can be composed of two to four spectrum vertices with at least one spectrum vertex from each side of the residue and a sequence vertex should include as many appropriate spectrum vertices as possible.
the sequence graph in figure  <dig> contains sequence vertices that are constructed from  <dig>   <dig> or  <dig> spectrum vertices.
sequence vertices are labeled with the m/z values of the included spectrum vertices.
any two sequence vertices that share one or more spectrum vertices are connected by a sequence edge.
there are two types of sequence edges, traversable edges and short-circuit edges.
a traversable sequence edge  connects two sequence vertices whose spectrum vertices can be fit into the interconnection pattern shown in figure  <dig>  allowing for missing spectrum vertices and spectrum edges.
a sequence edge is a short-circuit edge , if it cannot be a traversable edge.
figure  <dig> illustrates construction of sequence edges in a sequence graph.
a traversable sequence edge is used to connect two sequence vertices whose residues can be placed next to each other in a sequence tag.
a short-circuit edge is used to connect two vertices whose residues cannot be placed in a sequence tag regardless of whether they are next to each other or separated by other residues.
step 3: sequence tag searching
potential sequence tags for a tandem mass spectrum are identified by searching for paths in the sequence graph.
a path in a sequence graph is defined as a sequence of vertices connected by traversable edges.
a valid path is required to have no repeated vertex or traversable edge  and no short-circuit edge between any two vertices .
in the sequence graph of figure  <dig>  the saasgjt path and the saasgjv path are the two longest valid sequence paths.
the short circuit rule ensures that a path in a sequence graph corresponds to a legitimate interconnection in the spectrum graph for a sequence tag.
an example of invalid paths is the vjt path in the sequence graph of figure  <dig>  this path, corresponding to an invalid interconnection in the spectrum graph, is ruled out by the short circuit edge between vertices v and t in the sequence graph.
there are many possible paths in a non-trivial sequence graph.
the constraint of short-circuit edges for valid paths may complicate using the dynamic programming algorithm described previously for de novo sequencing  <cit> .
to identify optimum paths, the vonode algorithm uses a brute-force enumeration approach that simply finds all possible paths for subsequent evaluation with a scoring function.
compared to an analytical approach for finding optimum paths, the enumeration approach gives the flexibility to use virtually any scoring function and allows identification of not only the optimum path with the highest score, but also other top paths that rank below the optimum path.
path enumeration is efficient for sequence graphs because of the limited number of vertices and a low degree of connectivity in sequence graphs.
all possible paths in a sequence graph are found by iterating through every pair of vertices and identifying all possible paths between them.
let v and d be two vertices.
findpath  is a recursive function that finds all possible paths between v and d and returns them in a path list p. v is a temporary vertex list for storing vertices to be used to construct a path.
p and v are passed by reference between recursive function calls to save previous calculation results.
below is the pseudo-code for findpath:
findpath
<dig>     if any two vertices in v are connected by a short-circuit edge
<dig>        return
<dig>     push v onto the back of v
<dig>     if v and d are different vertices
<dig>        for every vertex, v', that is connected to v by a traversable edge and is not in v
<dig>           findpath
<dig>     else
<dig>        construct a path from v and save the path into p
<dig>     pop v out of the back of v
<dig>     return
all legitimate paths between a source vertex s and a destination vertex d are found with the functional call findpath, i.e., v and p are empty lists  in the beginning.
some sequence graphs can be divided into connected components.
a connected component is defined as a maximal subgraph connected by traversable edges.
for these sequence graphs, sequence paths from each component are found and evaluated independently of paths in other components.
step 4: sequence tag scoring
top sequence tags for a tandem mass spectrum are identified by scoring and ranking all valid paths in the sequence graph.
the score function used by the vonode algorithm is based on mass accuracy information of product ions measured in the tandem mass spectrum.
in the step of spectrum graph construction, every spectrum edge is assigned with a relative mass error, which is required to be less than the error tolerance .
the relative mass error is standardized to an edge weight by the function, ω = 2), where ε represents the relative mass error variable and ω represents the edge weight variable.
the function, pnorm, calculates the lower-tail cumulative probability for the variable ε from a normal distribution function with a mean of  <dig> and a standard deviation of Δ/ <dig>  because the relative mass error has a range of , the standardization assigns every spectrum edge a weight between  <dig>  and  <dig> .
the larger the relative mass error of a spectrum edge is, the less weight the spectrum edge has.
a sequence path is scored by enumerating all spectrum edges that are covered by the sequence path.
the score of a sequence path is simply the sum of the weights of all covered spectrum edges.
the top-scoring sequence paths in a sequence graph are those that cover many spectrum edges with low relative mass errors.
the top three sequence paths in figure  <dig> are saasgjt , aasgjt , and asgjt .
given a large set of tandem mass spectra, the vonode algorithm attempts de novo sequencing for all tandem mass spectra and then filters tandem mass spectra based on the score of the top sequence tag.
the default score cutoff is  <dig> .
proteome sample preparation
r. palustris cga <dig> strain was grown in defined growth medium to mid-log phase.
cells were harvested and lysed by sonication in ice-cold wash buffer.
cell lysates were then treated with  <dig> m guanidine and  <dig> mm dithiothreitol   at 60°c for  <dig> hour for protein denaturation and disulfide bond reduction.
after six-fold dilution with  <dig> mm tris-hcl/ <dig> mm cacl <dig> , the proteome sample was digested at 37°c with sequencing grade trypsin .
the sample was finally reduced with  <dig> mm dtt for  <dig> hour at 60°c and desalted using c <dig> solid-phase extraction .
lc-ms/ms analysis
the processed proteome sample was examined with a 24-hour two-dimensional liquid chromatography-tandem mass spectrometry analysis  as described previously  <cit> .
briefly, the sample was first separated by twelve-step strong cation ion exchange liquid chromatography and then by continuous gradient reverse phase liquid chromatography.
eluted peptides were electrosprayed at  <dig> -kv distal electrospray voltage into an ltq-orbitrap mass spectrometer .
tandem mass spectrometry analysis was performed with each full scan  followed by five data-dependent ms/ms scans at 35% normalized collision energy.
dynamic exclusion was enabled.
the full scans were acquired with 2-microscan averaging at resolution  <dig> , agc target  <dig> , and maximum ion injection time  <dig> ms. the ms/ms scans were acquired with 2-microscan averaging at resolution  <dig> , agc target  <dig> , and maximum ion time  <dig>  ms.
ms/ms data extraction
the proprietary finnigan raw files were converted to ft <dig> files and ft <dig> files with a visual basic program called raw2ft <dig>  the raw2ft <dig> program requires finnigan xdk  <dig>  to run.
the ft <dig> and ft <dig> file formats are simple extensions of the ms <dig> and ms <dig> file formats  <cit> , respectively, for high-resolution data.
in ms <dig> and ms <dig> files, every mass spectrum is represented with two columns of data for m/z and intensity.
in ft <dig> and ft <dig> files, every mass spectrum is represented with seven columns of data in the order of m/z, intensity, resolution, background, noise, and charge state, all of which are extracted from raw files.
all tandem mass spectra have header information for monoisotopic parent mass and charge state in ft <dig> files.
ms/ms data from other instrument venders need to be converted to the ft <dig> and ft <dig> formats to be analyzed by vonode.
accurate parent mass filtering of sequest identification
all ms/ms scans were searched with the sequest program  <cit>  against a concatenated forward and reverse r. palustris protein database with common protein contaminants   <cit> .
search results were reformatted from out files to sqt files  <cit> .
parent mass accuracy of all peptide identifications was calculated with the sqama program in three steps.
first, theoretical isotopic distribution of a peptide is calculated using its amino acid sequence and charge state.
then, observed isotopic distributions are found within ±  <dig> -da m/z windows of the expected isotopic peaks in the  <dig> full scans surrounding the ms/ms scan.
every isotopic peak in observed isotopic distributions represents an independent mass measurement.
finally, the mass error for a peptide identification is calculated as an average of all observed isotopic peaks' mass errors weighted by their intensities.
mass errors are reported in the original calcm+h+ field in the sqt files.
the dtaselect program  <cit>  was used to filter peptide identifications and to assemble peptides into proteins using the following parameters: retaining the duplicate ms/ms spectra for each peptide sequence , fully tryptic peptides only, with a delcn of at least  <dig>  and cross-correlation scores  of at least  <dig>  ,  <dig>  , and  <dig>  , and a minimum of two identified peptides for a protein.
identified peptides were further filtered by their parent mass errors calculated by sqama.
parent mass errors were normalized by shifting the median of the mass error distribution to zero for systematic mass error correction.
only peptide identifications with a normalized parent mass error less than  <dig>  da were retained as confident peptide identifications.
false discovery rates of peptide identification were calculated using the number of peptide identifications from reverse protein sequences.
performance benchmarking
the ft <dig> files of the benchmark dataset were input into the vonode program for de novo sequencing with the following parameters: relative mass error tolerance  =  <dig>  da; minimum sequence tag length =  <dig> .
for performance comparison, the benchmark dataset was also analyzed with the pepnovo v <dig>  program.
ms/ms scans in the ft <dig> files were formatted into individual dta files.
the default dta file format for sequest has m/z values with only one digit after the decimal point.
the dta files generated for pepnovo v <dig>  from ft <dig> files have m/z values with five digits after the decimal point to represent the high-resolution data and a measured parent ion charge state.
pepnovo was executed with the default orbitrap tryptic-peptide model .
pepnovo reports top  <dig> sequence tags for every ms/ms scan.
the ms/ms scans were filtered by the "prob" score of the top sequence tag.
sequence tags inferred by vonode and pepnovo for a spectrum were verified with the corresponding sequest identification.
all data processing was completed on a dell precision  <dig> workstation with an intel core  <dig> duo cpu and  <dig> gb ram.
RESULTS
orbitrap ms/ms measurement and benchmark dataset preparation
an r. palustris proteome was measured by 2d lc-ms/ms on an ltq-orbitrap instrument in the orbitrap ms/ms mode.
the 24-hour analysis yielded  <dig>  high-resolution ms/ms spectra.
at the configuration of resolution  <dig> and  <dig> microscan averaging, the scanning speed of orbitrap ms/ms was approximately  <dig> scans per minute.
as a comparison, the scanning speed of ltq ms/ms  is about  <dig> scans per minute.
the 2-fold decrease in scanning speed of orbitrap ms/ms reduced the number of ms/ms spectra acquired in the 24-hour 2d lc-ms/ms analysis.
figure  <dig> shows the distribution of relative mass errors between adjacent fragment ions in tandem mass spectra from the orbitrap ms/ms benchmark dataset.
for comparison, a distribution of relative mass errors from an ltq ms/ms dataset was shown in additional file  <dig>  figure s <dig>  this indicates that orbitrap ms/ms achieves much higher mass accuracy at the expense of a lower scanning speed.
to benchmark de novo sequencing accuracy, peptide identifications were first obtained from this r. palustris dataset using database searching and parent mass accuracy filtering.
concatenated forward and reverse database was used to measure false discovery rate of peptide identification  <cit> .
sequest identifications were assigned to  <dig>  tandem mass spectra using default dtaselect filtering criteria yielding a false discovery rate of  <dig> %.
further filtering with parent mass accuracy using the sqama program yielded identifications for  <dig>  spectra with a false discovery rate of  <dig> %.
in this study, we consider these identifications as gold standard and use them to verify sequence tags inferred by de novo sequencing algorithms.
de novo sequencing with the vonode algorithm
all  <dig>  ms/ms spectra were analyzed by the vonode algorithm in less than  <dig> minutes.
the de novo sequencing results were evaluated using the top sequence tag of a spectrum.
<dig>  sequenced spectra passed the score threshold of  <dig> , yielding sequence tags with an average length of  <dig>  residues .
for illustration, the de novo sequencing and verification results for spectra  <dig> -  <dig> in cycle  <dig> are shown in table  <dig>   <dig> spectra in this scan range have a sequence tag assignment, which consists of a sequence tag and two residual masses from the tag to the two termini of the peptide.
the two directions of a sequence tag  are equivalent.
isobaric amino acids l and i are not distinguished in de novo sequencing and they are represented by one letter, j, for convenience.
eight of these spectra have sequest identifications, which were matched to their sequence tags.
the sequence tag of a spectrum is verified by sequest to be correct if the sequence tag in one of the two directions matches exactly to the sequest peptide sequence.
this criterion of verifying a spectrum's sequence tag assignment is more stringent than some of those used in previous studies  <cit>  in that a spectrum can provide only one sequence tag  for verification and only an exact match of all residues in a sequence tag to the corresponding peptide sequence can be considered as correct.
* matched sections between the sequence tags and the sequest identifications are underlined.
* letter j represents amino acids l or i.
a global view of the de novo sequencing and verification results is shown with a venn diagram in figure 4a.
the universal set of all  <dig>  spectra is represented by the outer rectangle.
the set of  <dig>  spectra that have a confident sequest identification is represented by the circle in the left side.
the set of  <dig>  spectra that have the top sequence tag assignment by vonode is represented by the circle in the right side.
note that the sequest set and the vonode set do not completely overlap.
there is a set of  <dig>  sequest-only spectra that have a sequest identification but no vonode sequence tag assignment.
de novo sequencing requires measurement of fragmentation at more than  <dig> consecutive peptide bonds for inferring a sequence tag with a minimum length of  <dig> residues.
while fragmentation in these spectra could be informative for sequest identification, it may not be contiguous for de novo sequencing with vonode.
the intersection of the sequest set and the vonode set represents the  <dig>  spectra that have both a sequest identification and a sequence tag assignment.
eight spectra listed in table  <dig> belong to this category.
as shown in table  <dig>  this set of spectra can be further divided into two categories - correctly sequenced spectra and incorrectly sequenced spectra - based on the verification result.
the accuracy of de novo sequencing is defined as the percentage of the correctly sequenced spectra in the intersection set.
the accuracy of the top sequence tag assignment is 72% with  <dig>  correctly sequenced spectra and  <dig>  incorrectly sequenced spectra.
common types of errors in the incorrect sequence tags are described in the last section.
finally, there is a set of  <dig>  vonode-only spectra that have a sequence tag assignment but no sequest identification.
if we assume that the de novo sequencing accuracy calculated from the intersection spectra set remains approximately the same for the vonode-only spectra set, the majority of these sequence tags would provide correct partial sequence information for many unidentified peptides in the sample.
these unidentified peptides could be peptides with non-specific cleavages, peptides whose sequences are not in the protein sequence database  or peptides with chemical modifications .
the potential for mining out biological information from these unidentified peptides is precisely the motivation for developing the de novo sequencing approach that complements the database searching approach.
algorithm performance comparison
in this study, three figures of merit were used to evaluate the performance of the de novo sequencing algorithms.
the first figure of merit is the accuracy as defined above.
it is calculated from the intersection spectra as a simple estimate of the probability for a sequence tag assignment to be correct.
the second figure of merit is the average length of sequence tags inferred from a benchmark dataset.
a longer sequence tag is more informative and also more likely to be incorrect.
given the same accuracy, an algorithm that has larger average tag length is considered to be better.
the third figure of merit is the number of spectra that an algorithm can assign a sequence tag to in a benchmark dataset.
a larger percentage of sequenced spectra from a shotgun proteomics measurement can provide higher proteome coverage and higher average protein sequence coverage.
the de novo sequencing performance of vonode was evaluated using the three figures of merit at varying score thresholds and a constant minimum tag length threshold of three residues .
the figures of merit for the top sequence tag result filtered with the score thresholds of  <dig>  and  <dig>  are also shown in table  <dig>  by increasing the score threshold for filtering sequence tags, the accuracy and the average tag length were improved at the expense of greatly reduced number of de novo sequenced spectra.
the performance of vonode was compared to the pepnovo v <dig>  algorithm using the three figures of merits at varying score thresholds .
the pepnovo performance using thresholds of  <dig>  and  <dig>  are also shown in table  <dig>  the vonode results filtered at threshold  <dig>  have approximately the same average tag length as the pepnovo results.
the accuracy of vonode is better than pepnovo with either cutoff.
more importantly, vonode generated a much larger number of sequence tags than pepnovo from the same benchmark dataset.
the performance of vonode and pepnovo was also compared at different charge states.
spectra were grouped by parent ion charge states  and the performance was evaluated for each charge state group separately.
vonode performed equally well for charge state + <dig> and charge states + <dig> and higher, but much worse for charge state + <dig> .
pepnovo performed much better for charge state + <dig> than other charge states .
vonode and pepnovo had a similar performance for charge state + <dig>  but vonode outperformed pepnovo in the other two charge state groups.
the de novo sequencing performance of vonode and pepnovo was also compared at different ranges of mass coverage.
mass coverage is defined for a spectrum as the percentage of the parent peptide mass explained by a sequence tag.
mass coverage was designed to normalize the sequence tag size using the parent peptide size.
performance of vonode and pepnovo was compared in three mass coverage ranges: 0% ~20%, 20% ~40%, and 40% ~100% .
in the 0% ~20% range, vonode produced shorter sequence tags at higher accuracy from more spectra than pepnovo.
in the other two mass coverage ranges, vonode sequenced more spectra than pepnovo at comparable average tag length and accuracy.
the superior performance of vonode is attributed to two key algorithmic innovations.
first, a new type of spectrum graph was developed for sequence tag evaluation.
spectrum graphs were first proposed by bartels et al  <cit>  and have been used in many de novo sequencing algorithms.
in the bartels type of spectrum graphs, only one type of edge is used, which connects adjacent fragment ions of the same ion type.
artifact vertices are created to represent absent complementary ions for a lone y or b ion to capture the relationships between adjacent fragment ions of different ion types via those artifact vertices.
in this study, a new type of spectrum graph was developed to use four types of edges to represent the four possible relationships among adjacent fragment ions , avoiding creation of any artifact vertices.
every observed product ion is transformed to one and only one vertex in spectrum graph.
the score for a sequence tag is the total weight of all spectrum edges covered by the sequence tag.
this scoring function rewards a fragmentation site defined by a pair of complementary y and b ions much more than one defined by a lone y or b ion.
a residue derived from two adjacent pairs of complementary y and b ions is rewarded with the total weight of six spectrum edges; whereas a residue derived from two adjacent lone fragment ions is rewarded with the weight of only one spectrum edge .
second, the weight of a spectrum edge is calculated based on its relative mass error without using intensity information.
false edges connecting two unrelated ions were expected to be more likely to have a high relative mass error than true edges connecting two y or b ions.
based on the distribution of relative mass errors in the benchmark dataset , the relative mass error of a spectrum edge was standardized to a weight between  <dig> and  <dig>  higher edge weights correspond to lower relative mass errors.
this simplistic scoring function of weighing spectrum edges with relative mass errors was designed to take advantage of the improved mass accuracy, sensitivity, and dynamic range of orbitrap and ft-icr mass analyzers.
development of consensus sequence tag approach
if the top sequence tag of a spectrum is incorrect, the sequence tag with the second highest score for this spectrum could be correct.
one can use the top two sequence tags of a spectrum to match its sequest identification and consider this spectrum to be correctly sequenced if one of the top two sequence tags matches the sequest identification.
the accuracy of the top sequence tags at threshold  <dig>  was 72%.
by adding the second best sequence tag of every spectrum into consideration, the accuracy was improved to 82%.
adding the third best tag increased the accuracy further to 86%.
there was a diminishing return on the accuracy improvement by including more lower-ranking sequence tags.
considering multiple top ranking sequence tags for a spectrum conveniently improved the accuracy, but it would also complicate the subsequent step of using sequence tags for sequence polymorphism characterization and chemical modification identification.
a consensus sequence tag approach was proposed to obtain the significant accuracy gain of including the second best sequence tag without reporting two sequence tags for a spectrum.
a consensus sequence tag is simply the maximum common sub-sequence between the top two sequence tags in a spectrum.
it is guaranteed to be correct if at least one of the top two sequence tags is correct.
the vonode de novo sequencing results were analyzed with the consensus sequence tag approach at varying score thresholds .
consensus sequence tags were obtained from  <dig> spectra using a score threshold of  <dig>  and a minimum tag length of three residues .
figures of merit of this consensus sequence tags approach are shown in table  <dig>  the consensus tag of a spectrum is at least one residue shorter than the top sequence tag.
a spectrum with a consensus sequence tag shorter than  <dig> residues was discarded.
consensus sequence tags were also extracted from the pepnovo results using varying score thresholds .
the performance of the consensus sequence tag approach was compared to the top sequence tag approach for both vonode and pepnovo at different charge states and different mass coverage ranges .
compared to top sequence tags, consensus sequence tags have a greatly improved accuracy at the expense of reduced total number of sequenced spectra and lower average tag length .
top sequence tags from vonode and pepnovo are generally extensions of lower scoring tags or differ from lower scoring tags only in the end residues  and taking consensus sequence tags has the effect of trimming off unreliable residues from the ends of top sequence tags.
we think that the consensus sequence tag approach is a better balance among the three figures of merit  than the top sequence tag approach.
characterization of de novo sequencing errors
<dig> consensus sequence tags and  <dig> top sequence tags failed to match sequest identifications in the incorrectly sequenced spectral set .
the majority of these sequence tags are different from the corresponding sequest identifications by one or two residues.
the errors in those incorrect sequence tags are not random amino acid substitutions from their sequest identifications.
there were substitution errors that occur rarely, such as the substitution between two nearly isobaric amino acids, q and k. the masses of amino acids q and k are different by only  <dig>  da.
with ion trap ms/ms data, it is almost impossible to resolve such a small mass difference to distinguish these two amino acids.
in this orbitrap ms/ms dataset, there were only  <dig> % of incorrect sequence tags  that had the substitution error between amino acids q and k.
five common types of minor errors by vonode were characterized .
an incorrect sequence tag is categorized into one of the five error types if it can be corrected by making a single sequence change of that type.
many wrong sequence tags could be corrected by substituting an amino acid q with two amino acids g and a .
an example for this error type is the incorrect sequence tag for spectrum  <dig> in table  <dig>  the combined mass of g and a is exactly the same as the mass of q. when the fragment ions between g and a are missing in a spectrum, the residue doublets, ga or ag, would be mistakenly replaced by a single residue of q in the sequence tag.
in this benchmark dataset, a residue q in a sequence tag has an approximately 12% probability to actually be ga or ag.
this probability of the q assignment ambiguity should be taken into account when using a sequence tag containing q. for the same reason, the residue doublet, gg, can be mistaken for a single residue of n. together, these two types of errors account for 18% incorrect consensus sequence tags and 12% incorrect top sequence tags.
an interesting common type of de novo sequencing error is the inversion of two adjacent residues .
an example of this error type is a spectrum with the sequence tag of jqjyr and the sequest identification of r.fwtdqilyrl.-.
the sequence tag would match the sequest identification by inversing the two residues q and j in bold type.
inversions can involve any combination of amino acids.
the relative order of two adjacent residues in a sequence tag is determined from fragment ions between them.
it is difficult to explain why two adjacent residues can be mistakenly inversed so frequently.
note that, even if two adjacent residues in a peptide are indeed inversed from their order in the sequence database, sequest would still likely identify this peptide as the best match for the spectrum and report the peptide sequence in the sequence database.
a much larger percentage of incorrect sequence tags have a single wrong end residue than have a single wrong internal residue .
this position-dependent bias arises from vonode's tendency to extend a sequence tag to the longest possible.
this improves average tag length, but makes the end residues far more likely to be wrong than internal residues.
in light of this, it is recommended that, when matching a sequence tag to a sequence database, a mismatch at an end residue of the sequence tag should be considered as a probable de novo sequencing error.
together, these five types of minor errors account for 74% of incorrect top sequence tags and  <dig> % of incorrect consensus sequence tags.
if all the intersection spectra are considered, 84% of the consensus sequence tags match sequest identifications exactly,  <dig> % of them mismatch due to one of these minor errors, and only  <dig> % of them mismatch due to other types of errors.
similarly, there are only  <dig> % of top sequence tags from the intersection spectra that mismatch sequest identifications due to other types of errors.
therefore, de novo sequencing results should be used with consideration of these common types of minor errors.
CONCLUSIONS
in this study, a de novo sequencing algorithm, vonode, was developed specifically for high-resolution ms/ms data.
vonode has a unique scoring system that takes advantage of the excellent mass accuracy, sensitivity, and dynamic range of orbitrap and ft-icr mass analyzers.
the de novo sequencing performance of vonode was benchmarked in terms of accuracy, average sequence tag length, and total number of sequenced spectra using a 24-hour shotgun proteomics measurement of r. palustris.
using the new consensus sequence tag approach,  <dig>  sequence tags with an average length of  <dig>  were inferred at 84% accuracy from a total of  <dig>  input spectra.
this represents a significant improvement from the established pepnovo v <dig>  algorithm for analyzing high-resolution ms/ms data.
obtaining sequence tags is the first step towards identification of post-translational modifications and amino acid polymorphisms that may be missed by database searching algorithms  <cit> .
in future work, a separate algorithm will be developed to use sequence tags to search a protein sequence database and reconstruct many candidate peptides by considering a large number of chemical modifications  <cit>  or polymorphisms  <cit> .
to find the most likely modifications or polymorphisms, the candidate peptides will be evaluated by matching their theoretical spectra against the measured spectrum, which is analogous to the scoring strategy commonly used by database searching algorithms.
in this two-step approach, a de novo sequencing algorithm provides short sequence tags to constraint database searches for modifications or polymorphisms and a database-searching-like algorithm pinpoints optimum identifications.
we showed here that the vonode algorithm provides reliable de novo sequencing results from high-resolution ms/ms data.
authors' contributions
cp and nfs developed the vonode algorithm.
bhp designed the optimum path finding method.
whm and pac developed the sqama program.
ncv, jfb and rlh designed the study and acquired experimental data.
all authors read and approved the final manuscript for publication.
supplementary material
additional file 1
figure s <dig>  distribution of relative mass errors in an ltq ms/ms dataset.
comparison of distributions of relative mass errors indicates that orbitrap ms/ms  provides a much higher mass accuracy for de novo sequencing than ltq ms/ms.
click here for file
additional file 2
table s <dig>  top sequence tags inferred by vonode and their verification using sequest identification results.
click here for file
additional file 3
figure s <dig>  de novo sequencing performance comparison of vonode and pepnovo for peptides at different charge states.
the performance is analyzed for vonode top sequence tags , pepnovo top sequence tags , vonode consensus sequence tags , and pepnovo consensus sequence tags  from three different charge states .
the thresholds are  <dig>   <dig>  ...,  <dig> for vonode and  <dig> ,  <dig> , ...,  <dig>  for pepnovo.
the performance at each threshold is defined by the number of sequence spectra , the accuracy , and the average tag length .
click here for file
additional file 4
figure s <dig>  de novo sequencing performance comparison of vonode and pepnovo for sequence tags at different mass coverages.
the performance is analyzed for vonode top sequence tags , pepnovo top sequence tags , vonode consensus sequence tags , and pepnovo consensus sequence tags  from three ranges of mass coverages .
the thresholds are  <dig>   <dig>  ...,  <dig> for vonode and  <dig> ,  <dig> , ...,  <dig>  for pepnovo.
the performance at each threshold is defined by the number of sequence spectra , the accuracy , and the average tag length .
click here for file
additional file 5
table s <dig>  consensus sequence tags inferred by vonode and their verification using sequest identification results.
click here for file
acknowledgements
we thank d. pelletier for r. palustris cell samples.
we thank john yates' group at the scripps research institute for dtaselect and pavel pevzner's group at university of california at san diego for pepnovo v <dig> .
the computational work of this research was supported by the "ultrascale computational modeling of phenotype-specific metabolic processes in microbial communities" project from the u.s. department of energy, office of advanced scientific computing research and office of biological and environmental research.
the experimental work was supported by the u.s. department of energy, office of biological and environmental research, genomics: genomes to life program.
oak ridge national laboratory is managed by university of tennessee-battelle llc for the department of energy under contract doe-ac05-00or <dig>

 tandem mass spectrometry has become an important method for characterizing complex protein mixtures. since the emergence of this high-throughput technology, two complementary data analysis approaches have been pursued: a database searching approach and a de novo sequencing approach. the former identifies peptide sequences from a protein database by matching their predicted tandem mass spectra to measured tandem mass spectra; whereas the latter infers partial or complete peptide sequences directly from measured tandem mass spectra. due to its high identification accuracy and the rapid expansion of genomic sequence data, the database searching approach, enabled by popular algorithms such as sequest and mascot, is routinely used in current proteomics workflows. in contrast, although many de novo algorithms have been developed, they have not been widely used in high-throughput proteomics workflows. a high-throughput de novo sequencing capability is critically needed for detection of post-translational modifications, characterization of amino acid polymorphisms, and identification of proteins not represented in sequence databases. de novo sequencing has been actively pursued using ms/ms data acquired with ion trap instruments, which are the workhorses of many proteomics workflows. however, the relatively poor mass resolution, mass accuracy, and signal-to-noise ratio of ion trap ms/ms data is a large challenge for de novo sequencing. the basic idea of de novo sequencing is that, if the mass difference between two mass spectral peaks corresponds to an amino acid mass, the two peaks are likely two adjacent fragment ions flanking a residue of the peptide. because of the low mass accuracy of ion trap ms/ms data, it is common for two unrelated peaks to have a mass difference reasonably close to an amino acid mass by coincidence. additionally, in ion trap tandem mass spectra, low-intensity peaks of real fragment ions are often obscured by a large number of noise peaks, again interfering with de novo sequencing. in recent years, new hybrid mass spectrometers, such as ltq-orbitrap and ltq-ft from thermo fisher scientific inc., have become more common in proteomics workflows. these instruments combine the all-around ms/ms capability of ion trap with the excellent mass analysis capability of orbitrap and ft-icr. typical proteomics measurements take high-resolution full scans with orbitrap or ft-icr and ms/ms scans with ion trap to achieve accurate parent mass analysis and fast ms/ms acquisition. these hybrid instruments are also capable of acquiring high-resolution tandem mass spectra by performing peptide fragmentation in the front-end ion trap and then transferring fragment ions to the back-end orbitrap or ft-icr for mass analysis. such high-resolution ms/ms data is more amenable to de novo sequencing than ms/ms data acquired on conventional ion trap instruments. several de novo sequencing algorithms, including pepnovo, directag, peaks and msnovo, accept both ion trap ms/ms data and high-resolution ms/ms data. most of existing de novo sequencing algorithms can be adapted to high-resolution ms/ms data by tightening up mass error tolerance. de novo sequencing has also been combined with a ustag approach for ptm identification using ft-orbitrap ms/ms data. all these algorithms should obtain a significant performance boost by using high-resolution ms/ms data. here, we report a new de novo sequencing algorithm, vonode, to further exploit the potential of high-resolution ms/ms data by using a unique tag scoring function and a novel type of spectrum graphs. the scoring function of vonode relies more on mass accuracy information than on ion intensity information for scoring sequence tags. because of the improved dynamic range and sensitivity of high-resolution ms/ms data, fragment ions with lower intensity could just as likely be y and b ions as those with higher intensity. this is contrary to the intuitive assumption that lower-intensity peaks are less significant. a rigorous way for using intensity information is to model theoretical intensities in a spectrum for a sequence tag, which in turn requires building a reliable statistical model with comparable training data. in comparison, mass accuracy information in high-resolution ms/ms can be well defined statistically and is straightforward to use for scoring. to find sequence tags, many existing de novo sequencing algorithms reconstruct spectrum graphs where only adjacent fragment ions of the same ion type are connected. artifact vertices are used to represent non-existent complementary ions for lone y or b ions such that adjacent fragment ions of different ion types can be connected. vonode uses a new type of spectrum graph where every observed product ion is transformed to one and only one vertex and four types of edges are used to represent the four possible relationships among adjacent fragment ions. although this new type of spectrum graphs makes it algorithmically more difficulty to find sequence tags, it allows scoring of sequence tags based only on the ions observed in a mass spectrum. vonode was compared to an established de novo sequence algorithm, pepnovo v, to test whether these new features improves de novo sequencing. pepnovo v was adapted to high-resolution ms/ms data acquired on an ltq-ft instrument and its performance was shown to be significantly improved. this makes pepnovo v directly comparable to vonode. the de novo sequencing performance was benchmarked with high-resolution tandem mass spectra acquired from a 24-hour shotgun proteomics measurement of a bacterium rhodopseudomonas palustris. peptide sequences were first identified for this ms/ms dataset with the sequest-dtaselect toolchain. to further reduce the false discovery rate of database searching, peptide identifications were filtered with parent mass accuracy using a new perl program, called sqama. a total of spectra were identified with a false discovery rate of %. these confident peptide identifications were used to verify sequence tags generated by de novo sequencing algorithms. from this benchmark dataset, the vonode algorithm inferred sequence tags for spectra at an average length of residues using the consensus sequence tag approach. the accuracy of inferred consensus sequence tags was 84%. in comparison, the pepnovo v algorithm generated sequence tags for spectra with an average length of residues using a score cutoff of. the accuracy of top sequence tags from pepnovo v was 65%. note that vonode cannot be compared to a new version of pepnovo, pepnovo+, for high-resolution ms/ms data, because so far pepnovo+ has only one model for low-resolution ion trap ms/ms data. although many other de novo sequencing algorithms are available for additional performance benchmarking, the comparison of vonode to the established and widely-used pepnovo v. program showed that algorithmic concepts behind vonode's scoring function and the new type of spectrum graphs are important for de novo sequencing to take full advantage of high-resolution ms/ms data. methods algorithm description in an ms/ms measurement, a peptide is isolated by its m/z and fragmented with collision-induced dissociation. the product ions are then analyzed using an ms scan. most high-abundance product ions are y-ion type or b-ion type, generated from cleavage of peptide bonds. b-ions are fragments on the n-terminal side and numbered as b b and so on according to the number of residues they contain. y-ions are fragments on the c-terminal side and similarly numbered as y y and so on. other product ions can form directly from the cleavage of other bonds or indirectly from secondary fragmentation of primary product ions. besides product ions' peaks, tandem mass spectra are also populated with noise peaks. formally, let us define a tandem mass spectrum with a neutral parent ion mass p, a mass array {m m m..., mn in ascending order and a corresponding relative abundance array {a a a..., an. the mass-abundance pair has a mass of zero and a relative abundance of 100%. all other pairs, ≤ i ≤ n, correspond to neutral monoisotopic masses and relative abundances of measured product ions. mass spectral peaks are deisotoped and assigned a charge state in the pre-processing step by the vonode algorithm. peaks that fail in deisotoping are removed. the de novo sequencing problem is to infer partial sequences of a peptide from its tandem mass spectrum. a sequence tag is represented as mpr1r..rmmq, where r1r..rm is a sequence of amino acid residues and mp and mq are two residual masses to the two peptide termini. a residue ri, ≤ i ≤ m, belongs to an amino acid set a = {a, c, d, e, f, g, h, k, m, n, p, q, r, s, t, v, w, j, y}. let m be the mass for the amino acid Ω, Ω ∈ a. note that two isobaric amino acids, i and l, are represented with one letter, j, such that every amino acid in set a has a unique mass. sequence tags are bidirectional in that mpr1r..rmmq is equivalent to mqrmrm-..r1mp. a sequence tag for a tandem mass spectrum is considered correct, if the sequence tag, in either direction, matches exactly a portion of the peptide sequence. given multiple sequence tags inferred for a tandem mass spectrum, a longer sequence tag is more informative and, at the same time, more likely to be incorrect as the result of incorporation of a residue with wrong amino acid assignment. generally, de novo sequencing algorithms attempts to find the longest sequence tag that is correct for a certain probability. the vonode algorithm finds optimum sequence tags in four steps: spectrum graph construction, sequence graph construction, sequence tag searching, and sequence tag scoring. step 1: spectrum graph construction a spectrum graph is constructed from a tandem mass spectrum, given the amino acid set a. a vertex in the spectrum graph, vi, represents a product ion, ≤ i ≤ n. four types of edges are constructed in a spectrum graph, namely arrow edges, forward-slash edges, backslash edges, and vertical-bar edges. figure illustrates how edges in the spectrum graph are expected to connect y ions and b ions with one another. let Ω be an amino acid at the kth residue in a peptide of length residues. this residue is flanked by four product ions, yh, yh+ bk- and bk. an arrow edge is expected to connect a y ion to the next y ion or a b ion to the next b ion. a forward-slash edge is expected to connect a y ion with the next complementary b ion. a backslash edge is expected to connect a y ion with the previous complementary b ion. a vertical-bar edge is expected to connect two complementary y and b ions. given a set of vertices with unknown identity in a spectrum graph, edges are constructed between two vertices using their masses. let ε be the relative mass error for an edge, which is the difference between the measured mass combination of two vertices and the expected mass combination given amino acid masses ) and the parent mass. let Δ be the relative mass error tolerance. two vertices, vi and vj, with respective masses of mi and mj, ≤ i < j ≤ n and mi < mj, are connected by: an arrow edge, if | - m | = ε < Δ; a vertical-bar edge, if | - p | = ε < Δ; a forward-slash edge, if | p - - m | = ε < Δ; and a backslash edge, if | - p - m | = ε < Δ. the relative mass errors of spectrum edges are generally smaller than the mass errors of ions, because ion in a spectrum usually have mass errors in the same direction from out of mass calibration and the mass errors can cancel part of each other out in the relative mass error calculation. figure shows the spectrum graph constructed from a tandem mass spectrum of + peptide k.yrppaesaasgitvr.n. the y and b ions of this peptide could provide information for a sequence tag of saasgjt. two vertices that represent two adjacent y or b ions measured with sufficient mass accuracy should be connected by an edge of appropriate type. however, two vertices that are not related can also be connected from coincidence of their mass combination. every edge is associated with a relative mass error ε and an edge type. step 2: sequence graph construction a sequence graph is constructed from a spectrum graph to facilitate sequence tag searching. for clarity, vertices and edges in a sequence graph are referred to as sequence vertices and sequence edges respectively, whereas vertices and edges in a spectrum graph are referred to as spectrum vertices and spectrum edges respectively. a sequence vertex, representing an amino acid residue, is constructed from interconnected spectrum vertices that correspond to product ions on the two sides of the residue. these spectrum vertices should be interconnected by spectrum edges all labeled with this residue or vertical-bar spectrum edges. in figure sequence vertex Ω is constructed from spectrum vertices yh+ yh, bk- and bk and sequence vertex Ψ is constructed from spectrum vertices yh- yh, bk+ and bk. note that a spectrum vertex can be used for multiple sequence vertices. a sequence vertex for a residue can be composed of two to four spectrum vertices with at least one spectrum vertex from each side of the residue and a sequence vertex should include as many appropriate spectrum vertices as possible. the sequence graph in figure contains sequence vertices that are constructed from or spectrum vertices. sequence vertices are labeled with the m/z values of the included spectrum vertices. any two sequence vertices that share one or more spectrum vertices are connected by a sequence edge. there are two types of sequence edges, traversable edges and short-circuit edges. a traversable sequence edge connects two sequence vertices whose spectrum vertices can be fit into the interconnection pattern shown in figure allowing for missing spectrum vertices and spectrum edges. a sequence edge is a short-circuit edge, if it cannot be a traversable edge. figure illustrates construction of sequence edges in a sequence graph. a traversable sequence edge is used to connect two sequence vertices whose residues can be placed next to each other in a sequence tag. a short-circuit edge is used to connect two vertices whose residues cannot be placed in a sequence tag regardless of whether they are next to each other or separated by other residues. step 3: sequence tag searching potential sequence tags for a tandem mass spectrum are identified by searching for paths in the sequence graph. a path in a sequence graph is defined as a sequence of vertices connected by traversable edges. a valid path is required to have no repeated vertex or traversable edge and no short-circuit edge between any two vertices. in the sequence graph of figure the saasgjt path and the saasgjv path are the two longest valid sequence paths. the short circuit rule ensures that a path in a sequence graph corresponds to a legitimate interconnection in the spectrum graph for a sequence tag. an example of invalid paths is the vjt path in the sequence graph of figure this path, corresponding to an invalid interconnection in the spectrum graph, is ruled out by the short circuit edge between vertices v and t in the sequence graph. there are many possible paths in a non-trivial sequence graph. the constraint of short-circuit edges for valid paths may complicate using the dynamic programming algorithm described previously for de novo sequencing. to identify optimum paths, the vonode algorithm uses a brute-force enumeration approach that simply finds all possible paths for subsequent evaluation with a scoring function. compared to an analytical approach for finding optimum paths, the enumeration approach gives the flexibility to use virtually any scoring function and allows identification of not only the optimum path with the highest score, but also other top paths that rank below the optimum path. path enumeration is efficient for sequence graphs because of the limited number of vertices and a low degree of connectivity in sequence graphs. all possible paths in a sequence graph are found by iterating through every pair of vertices and identifying all possible paths between them. let v and d be two vertices. findpath is a recursive function that finds all possible paths between v and d and returns them in a path list p. v is a temporary vertex list for storing vertices to be used to construct a path. p and v are passed by reference between recursive function calls to save previous calculation results. below is the pseudo-code for findpath: findpath    if any two vertices in v are connected by a short-circuit edge       return    push v onto the back of v    if v and d are different vertices       for every vertex, v', that is connected to v by a traversable edge and is not in v          findpath    else       construct a path from v and save the path into p    pop v out of the back of v    return all legitimate paths between a source vertex s and a destination vertex d are found with the functional call findpath, i.e., v and p are empty lists in the beginning. some sequence graphs can be divided into connected components. a connected component is defined as a maximal subgraph connected by traversable edges. for these sequence graphs, sequence paths from each component are found and evaluated independently of paths in other components. step 4: sequence tag scoring top sequence tags for a tandem mass spectrum are identified by scoring and ranking all valid paths in the sequence graph. the score function used by the vonode algorithm is based on mass accuracy information of product ions measured in the tandem mass spectrum. in the step of spectrum graph construction, every spectrum edge is assigned with a relative mass error, which is required to be less than the error tolerance. the relative mass error is standardized to an edge weight by the function, ω = 2), where ε represents the relative mass error variable and ω represents the edge weight variable. the function, pnorm, calculates the lower-tail cumulative probability for the variable ε from a normal distribution function with a mean of and a standard deviation of Δ/ because the relative mass error has a range of, the standardization assigns every spectrum edge a weight between and. the larger the relative mass error of a spectrum edge is, the less weight the spectrum edge has. a sequence path is scored by enumerating all spectrum edges that are covered by the sequence path. the score of a sequence path is simply the sum of the weights of all covered spectrum edges. the top-scoring sequence paths in a sequence graph are those that cover many spectrum edges with low relative mass errors. the top three sequence paths in figure are saasgjt, aasgjt, and asgjt. given a large set of tandem mass spectra, the vonode algorithm attempts de novo sequencing for all tandem mass spectra and then filters tandem mass spectra based on the score of the top sequence tag. the default score cutoff is. proteome sample preparation r. palustris cga strain was grown in defined growth medium to mid-log phase. cells were harvested and lysed by sonication in ice-cold wash buffer. cell lysates were then treated with m guanidine and mm dithiothreitol at 60°c for hour for protein denaturation and disulfide bond reduction. after six-fold dilution with mm tris-hcl/ mm cacl, the proteome sample was digested at 37°c with sequencing grade trypsin. the sample was finally reduced with mm dtt for hour at 60°c and desalted using c solid-phase extraction. lc-ms/ms analysis the processed proteome sample was examined with a 24-hour two-dimensional liquid chromatography-tandem mass spectrometry analysis as described previously. briefly, the sample was first separated by twelve-step strong cation ion exchange liquid chromatography and then by continuous gradient reverse phase liquid chromatography. eluted peptides were electrosprayed at -kv distal electrospray voltage into an ltq-orbitrap mass spectrometer. tandem mass spectrometry analysis was performed with each full scan followed by five data-dependent ms/ms scans at 35% normalized collision energy. dynamic exclusion was enabled. the full scans were acquired with 2-microscan averaging at resolution, agc target, and maximum ion injection time ms. the ms/ms scans were acquired with 2-microscan averaging at resolution, agc target, and maximum ion time ms. ms/ms data extraction the proprietary finnigan raw files were converted to ft files and ft files with a visual basic program called raw2ft the raw2ft program requires finnigan xdk to run. the ft and ft file formats are simple extensions of the ms and ms file formats, respectively, for high-resolution data. in ms and ms files, every mass spectrum is represented with two columns of data for m/z and intensity. in ft and ft files, every mass spectrum is represented with seven columns of data in the order of m/z, intensity, resolution, background, noise, and charge state, all of which are extracted from raw files. all tandem mass spectra have header information for monoisotopic parent mass and charge state in ft files. ms/ms data from other instrument venders need to be converted to the ft and ft formats to be analyzed by vonode. accurate parent mass filtering of sequest identification all ms/ms scans were searched with the sequest program against a concatenated forward and reverse r. palustris protein database with common protein contaminants. search results were reformatted from out files to sqt files. parent mass accuracy of all peptide identifications was calculated with the sqama program in three steps. first, theoretical isotopic distribution of a peptide is calculated using its amino acid sequence and charge state. then, observed isotopic distributions are found within ± -da m/z windows of the expected isotopic peaks in the full scans surrounding the ms/ms scan. every isotopic peak in observed isotopic distributions represents an independent mass measurement. finally, the mass error for a peptide identification is calculated as an average of all observed isotopic peaks' mass errors weighted by their intensities. mass errors are reported in the original calcm+h+ field in the sqt files. the dtaselect program was used to filter peptide identifications and to assemble peptides into proteins using the following parameters: retaining the duplicate ms/ms spectra for each peptide sequence, fully tryptic peptides only, with a delcn of at least and cross-correlation scores of at least,, and, and a minimum of two identified peptides for a protein. identified peptides were further filtered by their parent mass errors calculated by sqama. parent mass errors were normalized by shifting the median of the mass error distribution to zero for systematic mass error correction. only peptide identifications with a normalized parent mass error less than da were retained as confident peptide identifications. false discovery rates of peptide identification were calculated using the number of peptide identifications from reverse protein sequences. performance benchmarking the ft files of the benchmark dataset were input into the vonode program for de novo sequencing with the following parameters: relative mass error tolerance = da; minimum sequence tag length =. for performance comparison, the benchmark dataset was also analyzed with the pepnovo v program. ms/ms scans in the ft files were formatted into individual dta files. the default dta file format for sequest has m/z values with only one digit after the decimal point. the dta files generated for pepnovo v from ft files have m/z values with five digits after the decimal point to represent the high-resolution data and a measured parent ion charge state. pepnovo was executed with the default orbitrap tryptic-peptide model. pepnovo reports top sequence tags for every ms/ms scan. the ms/ms scans were filtered by the "prob" score of the top sequence tag. sequence tags inferred by vonode and pepnovo for a spectrum were verified with the corresponding sequest identification. all data processing was completed on a dell precision workstation with an intel core duo cpu and gb ram.  orbitrap ms/ms measurement and benchmark dataset preparation an r. palustris proteome was measured by 2d lc-ms/ms on an ltq-orbitrap instrument in the orbitrap ms/ms mode. the 24-hour analysis yielded high-resolution ms/ms spectra. at the configuration of resolution and microscan averaging, the scanning speed of orbitrap ms/ms was approximately scans per minute. as a comparison, the scanning speed of ltq ms/ms is about scans per minute. the 2-fold decrease in scanning speed of orbitrap ms/ms reduced the number of ms/ms spectra acquired in the 24-hour 2d lc-ms/ms analysis. figure shows the distribution of relative mass errors between adjacent fragment ions in tandem mass spectra from the orbitrap ms/ms benchmark dataset. for comparison, a distribution of relative mass errors from an ltq ms/ms dataset was shown in additional file figure s this indicates that orbitrap ms/ms achieves much higher mass accuracy at the expense of a lower scanning speed. to benchmark de novo sequencing accuracy, peptide identifications were first obtained from this r. palustris dataset using database searching and parent mass accuracy filtering. concatenated forward and reverse database was used to measure false discovery rate of peptide identification. sequest identifications were assigned to tandem mass spectra using default dtaselect filtering criteria yielding a false discovery rate of %. further filtering with parent mass accuracy using the sqama program yielded identifications for spectra with a false discovery rate of %. in this study, we consider these identifications as gold standard and use them to verify sequence tags inferred by de novo sequencing algorithms. de novo sequencing with the vonode algorithm all ms/ms spectra were analyzed by the vonode algorithm in less than minutes. the de novo sequencing results were evaluated using the top sequence tag of a spectrum. sequenced spectra passed the score threshold of, yielding sequence tags with an average length of residues. for illustration, the de novo sequencing and verification results for spectra - in cycle are shown in table spectra in this scan range have a sequence tag assignment, which consists of a sequence tag and two residual masses from the tag to the two termini of the peptide. the two directions of a sequence tag are equivalent. isobaric amino acids l and i are not distinguished in de novo sequencing and they are represented by one letter, j, for convenience. eight of these spectra have sequest identifications, which were matched to their sequence tags. the sequence tag of a spectrum is verified by sequest to be correct if the sequence tag in one of the two directions matches exactly to the sequest peptide sequence. this criterion of verifying a spectrum's sequence tag assignment is more stringent than some of those used in previous studies in that a spectrum can provide only one sequence tag for verification and only an exact match of all residues in a sequence tag to the corresponding peptide sequence can be considered as correct. * matched sections between the sequence tags and the sequest identifications are underlined. * letter j represents amino acids l or i. a global view of the de novo sequencing and verification results is shown with a venn diagram in figure 4a. the universal set of all spectra is represented by the outer rectangle. the set of spectra that have a confident sequest identification is represented by the circle in the left side. the set of spectra that have the top sequence tag assignment by vonode is represented by the circle in the right side. note that the sequest set and the vonode set do not completely overlap. there is a set of sequest-only spectra that have a sequest identification but no vonode sequence tag assignment. de novo sequencing requires measurement of fragmentation at more than consecutive peptide bonds for inferring a sequence tag with a minimum length of residues. while fragmentation in these spectra could be informative for sequest identification, it may not be contiguous for de novo sequencing with vonode. the intersection of the sequest set and the vonode set represents the spectra that have both a sequest identification and a sequence tag assignment. eight spectra listed in table belong to this category. as shown in table this set of spectra can be further divided into two categories - correctly sequenced spectra and incorrectly sequenced spectra - based on the verification result. the accuracy of de novo sequencing is defined as the percentage of the correctly sequenced spectra in the intersection set. the accuracy of the top sequence tag assignment is 72% with correctly sequenced spectra and incorrectly sequenced spectra. common types of errors in the incorrect sequence tags are described in the last section. finally, there is a set of vonode-only spectra that have a sequence tag assignment but no sequest identification. if we assume that the de novo sequencing accuracy calculated from the intersection spectra set remains approximately the same for the vonode-only spectra set, the majority of these sequence tags would provide correct partial sequence information for many unidentified peptides in the sample. these unidentified peptides could be peptides with non-specific cleavages, peptides whose sequences are not in the protein sequence database or peptides with chemical modifications. the potential for mining out biological information from these unidentified peptides is precisely the motivation for developing the de novo sequencing approach that complements the database searching approach. algorithm performance comparison in this study, three figures of merit were used to evaluate the performance of the de novo sequencing algorithms. the first figure of merit is the accuracy as defined above. it is calculated from the intersection spectra as a simple estimate of the probability for a sequence tag assignment to be correct. the second figure of merit is the average length of sequence tags inferred from a benchmark dataset. a longer sequence tag is more informative and also more likely to be incorrect. given the same accuracy, an algorithm that has larger average tag length is considered to be better. the third figure of merit is the number of spectra that an algorithm can assign a sequence tag to in a benchmark dataset. a larger percentage of sequenced spectra from a shotgun proteomics measurement can provide higher proteome coverage and higher average protein sequence coverage. the de novo sequencing performance of vonode was evaluated using the three figures of merit at varying score thresholds and a constant minimum tag length threshold of three residues. the figures of merit for the top sequence tag result filtered with the score thresholds of and are also shown in table by increasing the score threshold for filtering sequence tags, the accuracy and the average tag length were improved at the expense of greatly reduced number of de novo sequenced spectra. the performance of vonode was compared to the pepnovo v algorithm using the three figures of merits at varying score thresholds. the pepnovo performance using thresholds of and are also shown in table the vonode results filtered at threshold have approximately the same average tag length as the pepnovo results. the accuracy of vonode is better than pepnovo with either cutoff. more importantly, vonode generated a much larger number of sequence tags than pepnovo from the same benchmark dataset. the performance of vonode and pepnovo was also compared at different charge states. spectra were grouped by parent ion charge states and the performance was evaluated for each charge state group separately. vonode performed equally well for charge state + and charge states + and higher, but much worse for charge state +. pepnovo performed much better for charge state + than other charge states. vonode and pepnovo had a similar performance for charge state + but vonode outperformed pepnovo in the other two charge state groups. the de novo sequencing performance of vonode and pepnovo was also compared at different ranges of mass coverage. mass coverage is defined for a spectrum as the percentage of the parent peptide mass explained by a sequence tag. mass coverage was designed to normalize the sequence tag size using the parent peptide size. performance of vonode and pepnovo was compared in three mass coverage ranges: 0% ~20%, 20% ~40%, and 40% ~100%. in the 0% ~20% range, vonode produced shorter sequence tags at higher accuracy from more spectra than pepnovo. in the other two mass coverage ranges, vonode sequenced more spectra than pepnovo at comparable average tag length and accuracy. the superior performance of vonode is attributed to two key algorithmic innovations. first, a new type of spectrum graph was developed for sequence tag evaluation. spectrum graphs were first proposed by bartels et al and have been used in many de novo sequencing algorithms. in the bartels type of spectrum graphs, only one type of edge is used, which connects adjacent fragment ions of the same ion type. artifact vertices are created to represent absent complementary ions for a lone y or b ion to capture the relationships between adjacent fragment ions of different ion types via those artifact vertices. in this study, a new type of spectrum graph was developed to use four types of edges to represent the four possible relationships among adjacent fragment ions, avoiding creation of any artifact vertices. every observed product ion is transformed to one and only one vertex in spectrum graph. the score for a sequence tag is the total weight of all spectrum edges covered by the sequence tag. this scoring function rewards a fragmentation site defined by a pair of complementary y and b ions much more than one defined by a lone y or b ion. a residue derived from two adjacent pairs of complementary y and b ions is rewarded with the total weight of six spectrum edges; whereas a residue derived from two adjacent lone fragment ions is rewarded with the weight of only one spectrum edge. second, the weight of a spectrum edge is calculated based on its relative mass error without using intensity information. false edges connecting two unrelated ions were expected to be more likely to have a high relative mass error than true edges connecting two y or b ions. based on the distribution of relative mass errors in the benchmark dataset, the relative mass error of a spectrum edge was standardized to a weight between and higher edge weights correspond to lower relative mass errors. this simplistic scoring function of weighing spectrum edges with relative mass errors was designed to take advantage of the improved mass accuracy, sensitivity, and dynamic range of orbitrap and ft-icr mass analyzers. development of consensus sequence tag approach if the top sequence tag of a spectrum is incorrect, the sequence tag with the second highest score for this spectrum could be correct. one can use the top two sequence tags of a spectrum to match its sequest identification and consider this spectrum to be correctly sequenced if one of the top two sequence tags matches the sequest identification. the accuracy of the top sequence tags at threshold was 72%. by adding the second best sequence tag of every spectrum into consideration, the accuracy was improved to 82%. adding the third best tag increased the accuracy further to 86%. there was a diminishing return on the accuracy improvement by including more lower-ranking sequence tags. considering multiple top ranking sequence tags for a spectrum conveniently improved the accuracy, but it would also complicate the subsequent step of using sequence tags for sequence polymorphism characterization and chemical modification identification. a consensus sequence tag approach was proposed to obtain the significant accuracy gain of including the second best sequence tag without reporting two sequence tags for a spectrum. a consensus sequence tag is simply the maximum common sub-sequence between the top two sequence tags in a spectrum. it is guaranteed to be correct if at least one of the top two sequence tags is correct. the vonode de novo sequencing results were analyzed with the consensus sequence tag approach at varying score thresholds. consensus sequence tags were obtained from spectra using a score threshold of and a minimum tag length of three residues. figures of merit of this consensus sequence tags approach are shown in table the consensus tag of a spectrum is at least one residue shorter than the top sequence tag. a spectrum with a consensus sequence tag shorter than residues was discarded. consensus sequence tags were also extracted from the pepnovo results using varying score thresholds. the performance of the consensus sequence tag approach was compared to the top sequence tag approach for both vonode and pepnovo at different charge states and different mass coverage ranges. compared to top sequence tags, consensus sequence tags have a greatly improved accuracy at the expense of reduced total number of sequenced spectra and lower average tag length. top sequence tags from vonode and pepnovo are generally extensions of lower scoring tags or differ from lower scoring tags only in the end residues and taking consensus sequence tags has the effect of trimming off unreliable residues from the ends of top sequence tags. we think that the consensus sequence tag approach is a better balance among the three figures of merit than the top sequence tag approach. characterization of de novo sequencing errors consensus sequence tags and top sequence tags failed to match sequest identifications in the incorrectly sequenced spectral set. the majority of these sequence tags are different from the corresponding sequest identifications by one or two residues. the errors in those incorrect sequence tags are not random amino acid substitutions from their sequest identifications. there were substitution errors that occur rarely, such as the substitution between two nearly isobaric amino acids, q and k. the masses of amino acids q and k are different by only da. with ion trap ms/ms data, it is almost impossible to resolve such a small mass difference to distinguish these two amino acids. in this orbitrap ms/ms dataset, there were only % of incorrect sequence tags that had the substitution error between amino acids q and k. five common types of minor errors by vonode were characterized. an incorrect sequence tag is categorized into one of the five error types if it can be corrected by making a single sequence change of that type. many wrong sequence tags could be corrected by substituting an amino acid q with two amino acids g and a. an example for this error type is the incorrect sequence tag for spectrum in table the combined mass of g and a is exactly the same as the mass of q. when the fragment ions between g and a are missing in a spectrum, the residue doublets, ga or ag, would be mistakenly replaced by a single residue of q in the sequence tag. in this benchmark dataset, a residue q in a sequence tag has an approximately 12% probability to actually be ga or ag. this probability of the q assignment ambiguity should be taken into account when using a sequence tag containing q. for the same reason, the residue doublet, gg, can be mistaken for a single residue of n. together, these two types of errors account for 18% incorrect consensus sequence tags and 12% incorrect top sequence tags. an interesting common type of de novo sequencing error is the inversion of two adjacent residues. an example of this error type is a spectrum with the sequence tag of jqjyr and the sequest identification of r.fwtdqilyrl.-. the sequence tag would match the sequest identification by inversing the two residues q and j in bold type. inversions can involve any combination of amino acids. the relative order of two adjacent residues in a sequence tag is determined from fragment ions between them. it is difficult to explain why two adjacent residues can be mistakenly inversed so frequently. note that, even if two adjacent residues in a peptide are indeed inversed from their order in the sequence database, sequest would still likely identify this peptide as the best match for the spectrum and report the peptide sequence in the sequence database. a much larger percentage of incorrect sequence tags have a single wrong end residue than have a single wrong internal residue. this position-dependent bias arises from vonode's tendency to extend a sequence tag to the longest possible. this improves average tag length, but makes the end residues far more likely to be wrong than internal residues. in light of this, it is recommended that, when matching a sequence tag to a sequence database, a mismatch at an end residue of the sequence tag should be considered as a probable de novo sequencing error. together, these five types of minor errors account for 74% of incorrect top sequence tags and % of incorrect consensus sequence tags. if all the intersection spectra are considered, 84% of the consensus sequence tags match sequest identifications exactly, % of them mismatch due to one of these minor errors, and only % of them mismatch due to other types of errors. similarly, there are only % of top sequence tags from the intersection spectra that mismatch sequest identifications due to other types of errors. therefore, de novo sequencing results should be used with consideration of these common types of minor errors.  in this study, a de novo sequencing algorithm, vonode, was developed specifically for high-resolution ms/ms data. vonode has a unique scoring system that takes advantage of the excellent mass accuracy, sensitivity, and dynamic range of orbitrap and ft-icr mass analyzers. the de novo sequencing performance of vonode was benchmarked in terms of accuracy, average sequence tag length, and total number of sequenced spectra using a 24-hour shotgun proteomics measurement of r. palustris. using the new consensus sequence tag approach, sequence tags with an average length of were inferred at 84% accuracy from a total of input spectra. this represents a significant improvement from the established pepnovo v algorithm for analyzing high-resolution ms/ms data. obtaining sequence tags is the first step towards identification of post-translational modifications and amino acid polymorphisms that may be missed by database searching algorithms. in future work, a separate algorithm will be developed to use sequence tags to search a protein sequence database and reconstruct many candidate peptides by considering a large number of chemical modifications or polymorphisms. to find the most likely modifications or polymorphisms, the candidate peptides will be evaluated by matching their theoretical spectra against the measured spectrum, which is analogous to the scoring strategy commonly used by database searching algorithms. in this two-step approach, a de novo sequencing algorithm provides short sequence tags to constraint database searches for modifications or polymorphisms and a database-searching-like algorithm pinpoints optimum identifications. we showed here that the vonode algorithm provides reliable de novo sequencing results from high-resolution ms/ms data. authors' contributions cp and nfs developed the vonode algorithm. bhp designed the optimum path finding method. whm and pac developed the sqama program. ncv, jfb and rlh designed the study and acquired experimental data. all authors read and approved the final manuscript for publication. supplementary material additional file 1 figure s distribution of relative mass errors in an ltq ms/ms dataset. comparison of distributions of relative mass errors indicates that orbitrap ms/ms provides a much higher mass accuracy for de novo sequencing than ltq ms/ms. click here for file additional file 2 table s top sequence tags inferred by vonode and their verification using sequest identification results. click here for file additional file 3 figure s de novo sequencing performance comparison of vonode and pepnovo for peptides at different charge states. the performance is analyzed for vonode top sequence tags, pepnovo top sequence tags, vonode consensus sequence tags, and pepnovo consensus sequence tags from three different charge states. the thresholds are..., for vonode and,,..., for pepnovo. the performance at each threshold is defined by the number of sequence spectra, the accuracy, and the average tag length. click here for file additional file 4 figure s de novo sequencing performance comparison of vonode and pepnovo for sequence tags at different mass coverages. the performance is analyzed for vonode top sequence tags, pepnovo top sequence tags, vonode consensus sequence tags, and pepnovo consensus sequence tags from three ranges of mass coverages. the thresholds are..., for vonode and,,..., for pepnovo. the performance at each threshold is defined by the number of sequence spectra, the accuracy, and the average tag length. click here for file additional file 5 table s consensus sequence tags inferred by vonode and their verification using sequest identification results. click here for file acknowledgements we thank d. pelletier for r. palustris cell samples. we thank john yates' group at the scripps research institute for dtaselect and pavel pevzner's group at university of california at san diego for pepnovo v. the computational work of this research was supported by the "ultrascale computational modeling of phenotype-specific metabolic processes in microbial communities" project from the u.s. department of energy, office of advanced scientific computing research and office of biological and environmental research. the experimental work was supported by the u.s. department of energy, office of biological and environmental research, genomics: genomes to life program. oak ridge national laboratory is managed by university of tennessee-battelle llc for the department of energy under contract doe-ac05-00or 
high-resolution tandem mass spectra can now be readily acquired with hybrid instruments, such as ltq-orbitrap and ltq-ft, in high-throughput shotgun proteomics workflows. to fully exploit the high mass accuracy of these spectra, a unique scoring system is proposed to evaluate sequence tags based primarily on mass accuracy information of fragment ions. consensus sequence tags were inferred for spectra with an average peptide length of residues from a total of input spectra acquired in a 24-hour proteomics measurement of rhodopseudomonas palustris. the accuracy of inferred consensus sequence tags was 84%. the improved spectral quality enables more accurate de novo sequencing for identification of post-translational modifications and amino acid polymorphisms. the vonode algorithm is freely available for download at http://compbio.ornl.gov/vonode. in this study, a new de novo sequencing algorithm, called vonode, has been developed specifically for analysis of such high-resolution tandem mass spectra. here, we improved de novo sequencing performance by developing a new algorithm specifically for high-resolution tandem mass spectral data.
 high-resolution tandem mass spectra can now be readily acquired with hybrid instruments, such as ltq-orbitrap and ltq-ft, in high-throughput shotgun proteomics workflows. the improved spectral quality enables more accurate de novo sequencing for identification of post-translational modifications and amino acid polymorphisms.  in this study, a new de novo sequencing algorithm, called vonode, has been developed specifically for analysis of such high-resolution tandem mass spectra. to fully exploit the high mass accuracy of these spectra, a unique scoring system is proposed to evaluate sequence tags based primarily on mass accuracy information of fragment ions. consensus sequence tags were inferred for spectra with an average peptide length of residues from a total of input spectra acquired in a 24-hour proteomics measurement of rhodopseudomonas palustris. the accuracy of inferred consensus sequence tags was 84%. according to our comparison, the performance of vonode was shown to be superior to the pepnovo v algorithm, in terms of the number of de novo sequenced spectra and the sequencing accuracy.  here, we improved de novo sequencing performance by developing a new algorithm specifically for high-resolution tandem mass spectral data. the vonode algorithm is freely available for download at http://compbio.ornl.gov/vonode. 