The first commonly used, automated de novo sequencing methods employed approaches like integer linear optimization , divide-and-conquer , and hidden Markov models . Graph-based approaches, such as Lutefisk97 , Sherenga , PEAKS , and PepNovo , represented MS/MS peaks as nodes, and mass differences between two observed peaks as edges. The highest-scoring path through the graph, from N-to C-terminus, was then used to infer the peptide sequence. In 2015, Muth et al. showed that, while de novo sequencing only had a 25% peptide overlap with traditional database searches, it often identified novel, unique peptides not present in the database, and provided critical insights by mapping these sequences to reference proteomes. From this, the authors considered de novo sequencing as a complementary approach, able to uncover additional peptide identifications that had been missed by traditional database search methods. However, they also noted that a robust method for validation of de novo sequencing results would be beneficial.