### Abstract

The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix subsequences, and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G = (V, E) where |V| = 2k+2, we can solve this problem in O(|V|+|E|) time and O(|V|) space using dynamic programming. Our approach can be further used to discover a modified amino acid in O(|V||E|) time and to analyze data with other types of noise in O(|V||E|) time. Our algorithms have been implemented and tested on actual experimental data.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | SIAM |

Pages | 389-398 |

Number of pages | 10 |

State | Published - Jan 1 2000 |

Event | 11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 9 2000 → Jan 11 2000 |

### Other

Other | 11th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | San Francisco, CA, USA |

Period | 1/9/00 → 1/11/00 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 389-398). SIAM.

}

*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.*SIAM, pp. 389-398, 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 1/9/00.

**Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry.** / Chen, Ting; Kao, Ming Yang; Tepel, Matthew; Rush, John; Church, George M.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

AU - Chen, Ting

AU - Kao, Ming Yang

AU - Tepel, Matthew

AU - Rush, John

AU - Church, George M.

PY - 2000/1/1

Y1 - 2000/1/1

N2 - The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix subsequences, and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G = (V, E) where |V| = 2k+2, we can solve this problem in O(|V|+|E|) time and O(|V|) space using dynamic programming. Our approach can be further used to discover a modified amino acid in O(|V||E|) time and to analyze data with other types of noise in O(|V||E|) time. Our algorithms have been implemented and tested on actual experimental data.

AB - The tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged prefix and suffix subsequences, and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G = (V, E) where |V| = 2k+2, we can solve this problem in O(|V|+|E|) time and O(|V|) space using dynamic programming. Our approach can be further used to discover a modified amino acid in O(|V||E|) time and to analyze data with other types of noise in O(|V||E|) time. Our algorithms have been implemented and tested on actual experimental data.

UR - http://www.scopus.com/inward/record.url?scp=0033881719&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033881719&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0033881719

SP - 389

EP - 398

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

PB - SIAM

ER -