Estimating the Accuracy of Protein Multiple Alignments Without a Reference

Estimating the accuracy of a computed multiple sequence alignment without knowing the correct alignment is an important problem. A good accuracy estimator has broad utility, from building a meta-aligner that selects the best output of a collection of aligners, to boosting the accuracy of a single aligner by choosing the best values for alignment parameters. The accuracy of a computed alignment is typically determined with respect to a reference alignment, by measuring the fraction of substitutions in the core columns of the reference alignment that are present in the computed alignment. We estimate accuracy without knowing the reference by learning a function that combines several easily-computable features of an alignment into a single value. For protein alignments, we consider 12 independent features that contribute to a quality alignment. An accuracy estimator is learned that is a polynomial function of these features; its coefficients are determined by minimizing its error with respect to true accuracy using mathematical programming. We evaluate this approach by applying it to the task of parameter advising, the problem of choosing alignment scoring parameters from a collection of parameter values in order to maximize the accuracy of a computed alignment. Accuracy is evaluated by comparing to a reference alignment from the BENCH (Edgar, 2009) and PALI (Balaji, 2001) benchmark suites of structurally aligned proteins. Compared to prior methods for selecting good alignments, our estimator outperforms both MOS (Lasmann and Sonnhammer, 2002) and NorMD (Thompson, et al., 2001) for parameter advising, and gives a 15.4 % boost in accuracy for the multiple alignment tool Opal (Wheeler and Kececioglu, 2007) on the hardest benchmarks. Accuracy Estimator Our estimator uses 12 feature functions fi(A) on an alignment A. Key aspects of a good feature function are: (1) it must be efficiently computable, (2) it must be normalized so fi is bounded by a constant, and finally (3) it should measure some attribute that differentiates high accuracy alignments from others. A few of these features are standard measures, but more than half are novel