|Speaker:||Tim Ting Chen|
Department of Genetics
Harvard Medical School
|Topic:||An Algorithm for Peptide Sequencing via Tandem Mass Spectrometry|
|Date:||Thursday, April 20, 2000|
|Place:||Gould-Simpson, Room 701|
A protein is a sequence of amino acids. Given a large number of molecules of the same protein, the tandem mass spectrometry fragments every protein into a prefix subsequence and a suffix subsequence (at a random location in the sequence), and then measures the masses of these subsequences. A set of such masses is called a spectrum. We are asked to find a protein sequence such that its fragmentation pattern best explains this spectrum, given that (1) it is unknown whether a mass corresponds to a prefix or suffix subsequence; (2) some subsequences disappear in the experiments and do not show up in the spectrum; (3) there are noise in the spectrum; (4) some amino acid is modified (ie. phosphorylated) but the modification is unknown.
We designed an algorithm which first converts a spectrum into a graph and then finds an optimal path on this graph. The algorithm is implemented and tested in the real experimental data successfully.