title: 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/.
authors.affiliation: Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA.
authors.forename: Sayed Mohammad Ebrahim
authors.initials: SM
authors.lastname: Sahraeian
authors.forename: Byung-Jun
authors.initials: BJ
authors.lastname: Yoon
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D011336:Probability; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein