Strings in proteomics and transcriptomics [Elektronische Ressource] : algorithmic and combinatorial questions in mass spectrometry and EST clustering / Zsuzsanna Lipták

Strings in Proteomics andTranscriptomicsAlgorithmic and Combinatorial Questionsin Mass Spectrometry and EST ClusteringZsuzsanna Lipta´kPhD thesis submitted to theTechnical Faculty of Bielefeld University, Germanyfor the degree of Dr. rer. nat.Supervised byDr. Sebastian Bo¨ckerRefereesDr. Sebastian Bo¨cker, Prof. Dr. Jens StoyeDefense onJuly 11, 2005for Nando347AbstractThis thesis treats two problem areas in bioinformatics which can both be benefi-cially formalized as string problems.The first (and larger) part deals with weighted string problems as they arisefrom biotechnological mass spectrometry applications. In a mass spectrometryexperiment—put in a simplified manner—the molecular mass of the sample mo-lecules is determined. The aim is to identify the sample, either with or withoutadditional information from a database, relying on the fact that the different build-ing blocks of proteins (namely, amino acids) and of DNA molecules (nucleotides)have different molecular masses. Viewing proteins and DNA molecules as strings,this leads naturally to the definition of weighted strings as strings over a finite+alphabet Σ with an additional weight (or mass) function :Σ→R .We develop some results in weighted string combinatorics, and then present ef-ficient algorithms for three weighted string problems which are motivated by massspectrometry.First, the mass decomposition problem is the problem of finding all compomerswhose mass equals a query mass.