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

Sahraeian SM, Yoon BJ - Nucleic Acids Res. (2010)

Bottom Line: Accurate tools for multiple sequence alignment (MSA) are essential for comparative studies of the function and structure of biological sequences.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA.

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/.

Show MeSH
Total CPU time for aligning the sequences in BAliBASE 3.0 (shown in seconds). For different implementations of PicXAA, the total CPU time is divided into two parts: the time that takes for probability estimation and the time needed in the remaining steps for constructing the alignment.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2926610&req=5

Figure 2: Total CPU time for aligning the sequences in BAliBASE 3.0 (shown in seconds). For different implementations of PicXAA, the total CPU time is divided into two parts: the time that takes for probability estimation and the time needed in the remaining steps for constructing the alignment.

Mentions: As shown in Figure 2, PicXAA-PF and PicXAA-PHMM has comparable speed with their progressive counterparts, ProbAlign and ProbCons. This implies that we can obtain more accurate MSAs, which effectively capture the local similarities among sequences, by using the proposed probabilistic greedy alignment approach without any substantial increase in the overall computational complexity compared with the conventional progressive approach. Further discussion on the computational complexity of PicXAA can be found in Supplementary Data.Figure 2.


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

Sahraeian SM, Yoon BJ - Nucleic Acids Res. (2010)

Total CPU time for aligning the sequences in BAliBASE 3.0 (shown in seconds). For different implementations of PicXAA, the total CPU time is divided into two parts: the time that takes for probability estimation and the time needed in the remaining steps for constructing the alignment.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2926610&req=5

Figure 2: Total CPU time for aligning the sequences in BAliBASE 3.0 (shown in seconds). For different implementations of PicXAA, the total CPU time is divided into two parts: the time that takes for probability estimation and the time needed in the remaining steps for constructing the alignment.
Mentions: As shown in Figure 2, PicXAA-PF and PicXAA-PHMM has comparable speed with their progressive counterparts, ProbAlign and ProbCons. This implies that we can obtain more accurate MSAs, which effectively capture the local similarities among sequences, by using the proposed probabilistic greedy alignment approach without any substantial increase in the overall computational complexity compared with the conventional progressive approach. Further discussion on the computational complexity of PicXAA can be found in Supplementary Data.Figure 2.

Bottom Line: Accurate tools for multiple sequence alignment (MSA) are essential for comparative studies of the function and structure of biological sequences.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.

View Article: PubMed Central - PubMed

Affiliation: Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA.

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/.

Show MeSH