title: Stochastic pairwise alignments.
abstract: BACKGROUND
  The level of sequence conservation between related nucleic acids or proteins often varies considerably along the sequence. Both regions with high variability (mutational hot-spots) and regions of almost perfect sequence identity may occur in the same pair of molecules. The reliability of an alignment therefore strongly depends on the level of local sequence similarity. Especially in regions of high variability, many alignments of almost equal quality exist, and the optimal alignment is highly arbitrary.
  
  
  RESULTS
  We discuss two approaches which deal with the inherent ambiguity of the alignment problem based on the computation of the partition function over all canonical pairwise alignments. The ensemble of possible alignments can be described by the probabilities P(ij) of a match between position i in the first and position j in the second sequence. Alternatively, we introduce a probabilistic backtracking procedure that generates ensembles of suboptimal alignments with correct statistical weights. A comparison between structure based alignments and large samples of stochastic alignments shows that the ensemble contains correct alignments with significant probabilities even though the optimal alignment deviates significantly from the structural alignment. Ensembles of suboptimal alignments obtained by stochastic backtracking can be used as input to any bioinformatics method based on pairwise alignment in order to gain reliability information not available from a single optimal alignment.
  
  
  BACKGROUND
  The software described in this contribution is available for downloading at http://www.tbi.univie.ac.at/~ulim/probA/
authors.affiliation: Institut für Theoretische Chemie und Molekulare Strukturbiologie Universität Wien, Vienna, Austria.
authors.forename: U
authors.initials: U
authors.lastname: Mückstein
authors.forename: I L
authors.initials: IL
authors.lastname: Hofacker
authors.forename: P F
authors.initials: PF
authors.lastname: Stadler
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D011506:Proteins / Q000032:analysis* / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D013269:Stochastic Processes
chemical_list: D011506:Proteins