Dataset Information

PicXAA: greedy probabilistic construction of maximum expected accuracy alignment of multiple sequences.

ABSTRACT: Accurate tools for multiple sequence alignment (MSA) are essential for comparative studies of the function and structure of biological sequences. However, it is very challenging to develop a computationally efficient algorithm that can consistently predict accurate alignments for various types of sequence sets. In this article, we introduce PicXAA (Probabilistic Maximum Accuracy Alignment), a probabilistic non-progressive alignment algorithm that aims to find protein alignments with maximum expected accuracy. PicXAA greedily builds up the multiple alignment from sequence regions with high local similarities, thereby yielding an accurate global alignment that effectively grasps the local similarities among sequences. Evaluations on several widely used benchmark sets show that PicXAA constantly yields accurate alignment results on a wide range of reference sets, with especially remarkable improvements over other leading algorithms on sequence sets with local similarities. PicXAA source code is freely available at: http://www.ece.tamu.edu/~bjyoon/picxaa/.

SUBMITTER: Sahraeian SM

PROVIDER: S-EPMC2926610 | biostudies-literature | 2010 Aug

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

PicXAA: greedy probabilistic construction of maximum expected accuracy alignment of multiple sequences.

Sahraeian Sayed Mohammad Ebrahim SM Yoon Byung-Jun BJ

Nucleic acids research 20100422 15

Accurate tools for multiple sequence alignment (MSA) are essential for comparative studies of the function and structure of biological sequences. However, it is very challenging to develop a computationally efficient algorithm that can consistently predict accurate alignments for various types of sequence sets. In this article, we introduce PicXAA (Probabilistic Maximum Accuracy Alignment), a probabilistic non-progressive alignment algorithm that aims to find protein alignments with maximum expe ...[more]

PMID: 20413579

Similar Datasets

Project description:BACKGROUND: Since RNA molecules regulate genes and control alternative splicing by allostery, it is important to develop algorithms to predict RNA conformational switches. Some tools, such as paRNAss, RNAshapes and RNAbor, can be used to predict potential conformational switches; nevertheless, no existent tool can detect general (i.e., not family specific) entire riboswitches (both aptamer and expression platform) with accuracy. Thus, the development of additional algorithms to detect conformational switches seems important, especially since the difference in free energy between the two metastable secondary structures may be as large as 15-20 kcal/mol. It has recently emerged that RNA secondary structure can be more accurately predicted by computing the maximum expected accuracy (MEA) structure, rather than the minimum free energy (MFE) structure. RESULTS: Given an arbitrary RNA secondary structure S? for an RNA nucleotide sequence a = a?,..., a(n), we say that another secondary structure S of a is a k-neighbor of S?, if the base pair distance between S? and S is k. In this paper, we prove that the Boltzmann probability of all k-neighbors of the minimum free energy structure S? can be approximated with accuracy ? and confidence 1 - p, simultaneously for all 0 ? k < K, by a relative frequency count over N sampled structures, provided that N>N(?,p,K)=??¹(p/2K)²/4?², where ?(z) is the cumulative distribution function (CDF) for the standard normal distribution. We go on to describe the algorithm RNAborMEA, which for an arbitrary initial structure S? and for all values 0 ? k < K, computes the secondary structure MEA(k), having maximum expected accuracy over all k-neighbors of S?. Computation time is O(n³ · K²), and memory requirements are O(n² · K). We analyze a sample TPP riboswitch, and apply our algorithm to the class of purine riboswitches. CONCLUSIONS: The approximation of RNAbor by sampling, with rigorous bound on accuracy, together with the computation of maximum expected accuracy k-neighbors by RNAborMEA, provide additional tools toward conformational switch detection. Results from RNAborMEA are quite distinct from other tools, such as RNAbor, RNAshapes and paRNAss, hence may provide orthogonal information when looking for suboptimal structures or conformational switches. Source code for RNAborMEA can be downloaded from http://sourceforge.net/projects/rnabormea/ or http://bioinformatics.bc.edu/clotelab/RNAborMEA/.

Dataset Information

PicXAA: greedy probabilistic construction of maximum expected accuracy alignment of multiple sequences.

Publications

PicXAA: greedy probabilistic construction of maximum expected accuracy alignment of multiple sequences.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets