Peptide sequencing via graph path decomposition

In proteomics, an important problem is to determine the amino acids sequence of a short peptide solely from its tandem mass spectrometry spectrum. Previous work has shown that a spectrum can be modeled with a directed acyclic graph and the amino acids sequence of the peptide can be obtained by computing the longest antisymmetric path in the graph. In this paper, we study the longest antisymmetric path in a general directed acyclic graph and show that the problem can be solved in linear time when both the number of symmetric vertex pairs and the path width of the graph are bounded from above by constants. We have implemented this linear time algorithm and tested its performance on experimental spectrums. Our testing results suggest that the algorithm can efficiently process the MS/MS spectrum of a peptide and provide sequencing results of high accuracy. Since the algorithm does not impose any additional requirements on the structures of the underlying directed acyclic graph, it might be of independent interest and can potentially be applied to problems of similar nature in software testing and software validation.