Bioinformatics Vol. 18 no. 90002 2002
Pages S153-S160
© 2002 Oxford University Press
Stochastic pairwise alignments
1 Institut für Theoretische Chemie und Molekulare Strukturbiologie
Universität Wien, Währingerstraße 17, Vienna A-1090, Austria
2 The Santa Fe Institute, Santa Fe, New Mexico, USA
Received on April 8, 2002
; accepted on June 15, 2002
Motivation: 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 Pij 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.
Availability: The software described in this contribution is available for downloading at http://www.tbi.univie.ac.at/~ulim/probA/
Contact: ivo{at}tbi.univie.ac.at
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Morita, Y. Saito, K. Sato, K. Oka, K. Hotta, and Y. Sakakibara Genome-wide searching with base-pairing kernel functions for noncoding RNAs: computational and expression analysis of snoRNA families in Caenorhabditis elegans Nucleic Acids Res., February 1, 2009; 37(3): 999 - 1009. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 X. Xu, Y. Ji, and G. D. Stormo RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment Bioinformatics, August 1, 2007; 23(15): 1883 - 1891. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Ferre, Y. Ponty, W. A. Lorenz, and P. Clote DIAL: a web server for the pairwise alignment of two RNA three-dimensional structures using nucleotide, dihedral angle and base-pairing similarities Nucleic Acids Res., July 13, 2007; 35(suppl_2): W659 - W668. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
U. Roshan and D. R. Livesay Probalign: multiple sequence alignment using partition function posterior probabilities Bioinformatics, November 15, 2006; 22(22): 2715 - 2721. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Chivian and D. Baker Homology modeling using parametric alignment ensemble generation with consensus and energy-based model selection Nucleic Acids Res., October 18, 2006; 34(17): e112 - e112. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Ferre and P. Clote BTW: a web server for Boltzmann time warping of gene expression time series. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W482 - W485. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. E. Abbas and S. P. Holmes Bioinformatics and Management Science: Some Common Tools and Techniques Operations Research, March 1, 2004; 52(2): 165 - 190. [Abstract] [PDF]
|
|