title: MaxSubSeq: an algorithm for segment-length optimization. The case study of the transmembrane spanning segments.
abstract: BACKGROUND
  A problem in predicting the topography of transmembrane proteins is the optimal localization of the transmembrane segments along the protein sequences, provided that each residue is associated with a propensity of being or not being included in the transmembrane protein region. From previous work it is known that post-processing of propensity signals with suited algorithms can greatly improve the quality and the accuracy of the predictions. In this paper we describe a general dynamic programming-like algorithm (MaxSubSeq, Maximal SubSequence) specifically designed to optimize the number and length of segments with constrained length in a given protein sequence. Previous application of our algorithm, has proved its effectiveness in the optimization task of both neural network and hidden Markov models output, and in this paper we present the detailed description of MaxSubSeq.
  
  
  RESULTS
  We describe the application of MaxSubSeq to the location of both helical and beta strand transmembrane segments, optimizing the outputs derived with different predictive algorithms. For all-alpha transmembrane proteins we use both the standard Kyte-Doolittle (KD) hydropathy scale and the TMHMM predictor (http://www.cbs.dtu.dk/). Using a set of 188 well characterized membrane proteins, MaxSubSeq nearly doubles the correct location of transmembrane segments as compared to the standard KD hydrophobicity plot, reaching 51% accuracy. If MaxSubSeq is used to optimize the TMHMM method the accuracy increases from 68 to 72%. When used to regularize the prediction of beta transmembrane strands, obtained using both a neural network and a HMM based predictors, MaxSubSeq increases the accuracy per protein up to 72 and 73% respectively.
  
  
  BACKGROUND
  The program is available upon request to the authors, or it is accessible through our web server (http://gpcr.biocomp.unibo.it/predictors/)
authors.affiliation: Department of Biology/CIRB, University of Bologna, via Irnerio 42, 40126 Bologna, Italy. piero@biocomp.unibo.it
authors.forename: Piero
authors.initials: P
authors.lastname: Fariselli
authors.forename: Michele
authors.initials: M
authors.lastname: Finelli
authors.forename: Davide
authors.initials: D
authors.lastname: Marchignoli
authors.forename: Pier Luigi
authors.initials: PL
authors.lastname: Martelli
authors.forename: Ivan
authors.initials: I
authors.lastname: Rossi
authors.forename: Rita
authors.initials: R
authors.lastname: Casadio
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D000252:Calcium-Transporting ATPases / Q000737:chemistry; D002417:Cattle; D003576:Electron Transport Complex IV / Q000737:chemistry; D008565:Membrane Proteins / Q000737:chemistry* / Q000235:genetics; D008968:Molecular Conformation; D008969:Molecular Sequence Data; D018272:Porins / Q000737:chemistry; D011786:Quality Control; D011817:Rabbits; D015203:Reproducibility of Results; D012486:Salmonella typhimurium / Q000737:chemistry; D012519:Sarcoplasmic Reticulum / Q000737:chemistry; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
chemical_list: D008565:Membrane Proteins; D018272:Porins; D003576:Electron Transport Complex IV; D000252:Calcium-Transporting ATPases