BACKGROUND
aligning multiple evolutionarily related protein sequences is a fundamental technique for studying protein function, structure, and evolution.
multiple sequence alignment methods are often an essential component for solving challenging bioinformatics problems such as protein function prediction, protein homology identification, protein structure prediction, protein interaction study, mutagenesis analysis, and phylogenetic tree construction.
during the last thirty years or so, a number of methods and tools have been developed for multiple sequence alignment, which have made fundamental contributions to the development of the bioinformatics field.
state of the art multiple sequence alignment methods adapt some popular techniques to improve alignment accuracy, such as iterative alignment  <cit> , progressive alignment  <cit> , alignment based on profile hidden markov models  <cit> , and posterior alignment probability transformation  <cit> .
some alignment methods, such as 3d-coffee  <cit>  and promals3d  <cit> , use 3d structure information to improve multiple sequence alignment, which cannot be applied to the majority of protein sequences without tertiary structures.
in order to overcome this problem, we have developed a method to incorporate secondary structure, relative solvent accessibility, and contact map information predicted from protein sequences into multiple sequence alignment.
predicted secondary structure information has been used to improve pairwise sequence alignment  <cit> , but few attempts had been made to use predicted secondary structure information in multiple sequence alignment  <cit> .
to the best of our knowledge, applying predicted relative solvent accessibility and residue-residue contact map to multiple sequence alignment is novel.
in order to use the predicted structural information to advance the state of the art of multiple sequence alignment, we first compared the existing multiple sequence alignment tools  <cit>  on the standard benchmark data sets such as balibase  <cit> , sabmark  <cit>  and oxbench  <cit> , which showed that mafft  <cit> , t-coffee  <cit> , msaprobs  <cit> , and probcons  <cit>  yielded the best performance.
then we developed msacompro, a new multiple sequence alignment method, which effectively utilizes predicted secondary structure, relative solvent accessibility, and residue-residue contact map together with posterior alignment probabilities produced by both pair hidden markov models and partition function as in msaprobs  <cit> .
the assessment results of msacompro compared to the benchmark data sets from balibase, sabmark and oxbench showed that incorporating predicted structural information has improved the accuracy of multiple sequence alignment over most existing tools without using structural features and sometimes the improvement is substantial.
method
following the general scheme in msaprobs  <cit> , msacompro has five main steps:  compute the pairwise posterior alignment probability matrices based on both pair-hmm and partition function, considering the similarity in amino acids, secondary structure, and relative solvent accessibility;  generate the pairwise distance matrix from both the pairwise posterior probability matrices constructed in the first step and the pairwise contact map similarity matrices;  construct a guide tree based on pairwise distance matrix, and calculate sequence weights;  transform all the pairwise posterior matrices by a weighting scheme;  perform a progressive alignment by computing the profile-profile alignment from the probability matrices of all sequence pairs, and then an iterative alignment to refine the results from progressive alignment.
our method is different from msaprobs in that it adds secondary structure and solvent accessibility information to the calculation of the posterior residue-residue alignment probabilities and computes the pairwise distance matrix with the help of predicted residue-residue contact information.
construction of pairwise posterior probability matrices based on amino acid sequence, secondary structure and solvent accessibility information
for two protein sequences x and y in a sequence group s to be aligned, we denote x = , y = , where x <dig>  x <dig> ......, xn <dig> and y <dig>  y <dig> ......,yn <dig> are lists of the residues in x and y, respectively.
n <dig> is the length of sequence x, and n <dig> is the length of sequence y. suppose xi is the i-th amino acid in sequence x, and yj is the j-th amino acid in sequence y. we let aln denote a global alignment between x and y, aln the set of of all the possible global alignments of x and y, and aln* ∈ aln the true pairwise alignment of x and y. the posterior probability that the i-th residue in x  is aligned to the j-th residue  in y in aln* is defined as:
p=∑aln∈alnpi{xi~yj∈aln}
i{xi~yj∈aln}={ <dig> iftrueo,otherwise
p denotes the probability that aln is the true alignment aln*: thus, the posterior probability n <dig> × n <dig> matrix pxy is a collection of all the values p  for short) for  <dig> ≤ xi ≤ n <dig>   <dig> ≤ yj ≤ n <dig>  the calculation process of the pairwise posterior probability matrix is described as follows.
as in msaprobs, two different methods  are used to compute the pairwise posterior probability matrices , respectively.
the first kind of pairwise probability matrix pxy <dig> is calculated by a partition function  of alignments based on dynamic programming.
f denotes the probability of all partial global alignments of x and y ending at position .
fm  is the probability of all partial global alignments with xi aligned to yj, fy, is the probability of all partial global alignments with yj aligned to a gap, and fx is the probability of all partial global alignments with xi aligned to a gap.
accordingly, the partition function can be calculated recursively as follows:
fm=few1βs+w2ss,ss)+w3sa,sa)
fy=fmeβgap+fyeβext
fx=fmeβgap+fxeβext
f=fm+fy+fx
subject to the constraint w <dig> + w <dig> + w <dig> =  <dig>
in the formula above, s is the amino acid similarity score between xi and yj.
one element of the substitution matrix s, ss, ss) is the similarity score between the secondary structure ) of residue xi in protein x and that of residue yj in protein y according to the secondary structure similarity matrix ss, sa, sa) is the similarity score between the relative solvent accessibility ) of residue xi in protein x and that of residue yj in protein y according to the solvent accessibility similarity matrix sa.
w <dig>  w <dig>  w <dig> are weights used to control the influence of the amino acid substitution score, secondary structure similarity score, and solvent accessibility similarity score.
the secondary structure and solvent accessibility can be automatically predicted by sspro/accpro  <cit>   using a multi-threading technique implemented in msacompro, or alternatively be provided by a user.
the values of the three weights are set to  <dig> ,  <dig> , and  <dig>  by default, and can be adjusted by users.
the ensembles of bidirectional recurrent neural network architectures in accpro are used to discriminate between two different states of relative solvent accessibility, higher or lower than the accessibility cutoff - 25% of the total surface area of a residue  <cit> , corresponding to e or b. as in msaprobs, β is a parameter measuring the deviation between suboptimal and optimal alignments, gap is the gap open penalty, and ext is the gap extension penalty.
we used the gonnet  <dig> matrix as a substitution matrix to generate the similarity scores between two amino acids in proteins  <cit> .
the  <dig> ×  <dig> secondary structure similarity matrix ss contains the similarity scores of three kinds of secondary structures  as follows:
ss= <dig>
, where two identical secondary structures receive a score of  <dig> and different ones receive a score of  <dig>
the  <dig> ×  <dig> solvent accessibility similarity matrix sa contains the similarity scores of two kinds of relative solvent accessibilities  as follows:
sa= <dig>
, where two identical solvent accessibilities receive a score of  <dig> and different ones receive a  <dig>  it is worth noting that we used the simple identity scoring matrix for secondary structure and solvent accessibility here.
employing more advance scoring matrices defined in  <cit>  may lead to further improvement.
each posterior residue-residue alignment probability element in the first kind of posterior probability matrix  can be calculated from the partition function as:
p1=fmfm'f•ew1βs+w2ss,ss)+w3sa,sa)
, where fm′ denotes the partition function of all the reverse alignments starting from the position  till position  with xi aligned to yj.
as in msaprobs, the second kind of pairwise probability matrix pxy <dig> is calculated by a pair hidden markov model  combining both forward and backward algorithm  <cit> .
the pairwise probabilities can be generated under the guidance of pair hmm involving state emissions and transitions.
pxy <dig> is only derived from protein sequences without using secondary structure and solvent accessibility, which is different from promals  <cit>  that lets hmm emit both amino acids and secondary structure alphabets.
the final posterior probability matrix pxy is calculated as the root mean square of the corresponding values in pxy <dig> and pxy <dig> as follows.
p=p12+p <dig>
where p <dig> and p <dig> denote a posterior probability element in two kinds of posterior probability matrices , respectively.
construction of pairwise distance matrices based on pairwise posterior probabilities and pairwise contact map scores
the posterior probability matrix pxy is used as a scoring function to generate a pairwise global alignment between sequences x and y. the optimal global alignment score opt of the global alignment is computed according to an optimal sub-alignment score matrix as.
the optimal sub-alignment score as denotes the score of the optimal sub-alignment ending at residues i and j in x and y. the as matrix is recursively calculated as:
as=max{as+pxyasas
as  is the optimal score of the full global alignment between x and y, which is denoted as optscore.
in addition to the optimal alignment score, we introduce a contact map score, cmscore, for the optimal pairwise alignment of x and y, assuming that the spatially neighboring residues of two aligned residues should have a higher tendency to be aligned together.
cmscore is calculated from the contact map correlation score matrix cmapxy based on the residue-residue contact map matrices cmapx and cmapy of x and y.
assuming the optimal global alignment of x and y is represented as,
x1x <dig> ......-xm......xp......xn1y1-......ykyk+ <dig> ....-......yn <dig>
we can generate a new alignment after removing the pairs containing gaps:
x <dig> ......xm............xn1y <dig> .....yk+ <dig> ..........yn <dig>
, which can be denoted as
x1′x2′............xn′y1′y2′...........yn′
, where n is the length of the new alignment without gaps
from this alignment, we can construct two contact map matrices, cmapx and cmapy, shown below:
cmapx=x11′x12′......x1n′x21′x22′......x2n′......................................xn1′xn2′......xnn′
cmapy=y11′y12′......y1n′y21′y22′......y2n′......................................yn1′yn2′......ynn′
xij′ is the contact probability score between amino acid xi′ and xj′ in protein sequence x, and yij′ is the contact probability score between amino acid yi' and yj' in protein sequence y. the residue-residue contact probabilities are predicted from the sequence by nncon  <cit>  .
the contact map correlation score matrix cmapxy is calculated as the multiplication of cmapx and cmapy:
cmapxy=cmapx×cmapy=xy11′xy12′....xy1n′xy21′xy22′....xy2n′............................................xyn1′xyn2′....xynn′
xyii′ is the contact map score for an aligned residue pair .
the contact map score for the global alignment of two sequences x and y is calculated as
cmscore=1n <dig> ∑i=1ncmapxy=1n <dig> ∑i=1nxyii′=1n <dig> ∑i=1n∑j=1nxij′yji′
in practice, we only need to calculate the diagonal values in cmapxy.
finally, we define the pairwise distance between sequences x and y as
d=1-w4optscoremin{n <dig> n2}-w5cmscore
, where w <dig> + w <dig> =  <dig>  the weights w <dig> and w <dig> are used to control the influence of sequences x and y.
construction of guide tree and transformation of posterior probability
akin to msaprobs  <cit> , a guide tree is constructed by the upgma method that uses the linear combinatorial strategy  <cit> .
the distance between a new cluster z formed by merging clusters x and y, and another cluster w is calculated as :
d=d×num+d×numnum+num
in which num is the number of leafs in cluster x.
after the guide tree is constructed, sequences are weighted according to the schemes inferred in  <cit> .
to reduce the bias of sampling similar sequences, we use a weighted scheme to transform the former posterior probability as
pxy′=1wnpxy+ ∑z∈s,z≠x,ywzpxzpzy)
wx and wy are, respectively, the weight of sequences x and y, wz is the weight of a sequence z other than x or y in the given group of sequences, and wn is the sum of sequence weights in dataset s.
combination of progressive and iterative alignment
we first use the guide tree to generate a multiple sequence alignment by progressively aligning two clusters of the most similar sequences together.
as in msaprobs  <cit> , we also apply a weighted profile-profile alignment to align two clusters of sequences.
the sequence weights are the same as in the previous step.
the posterior alignment probability matrix of two clusters/profiles is averaged from the probability matrices of all sequence pairs , where x and y are from the two different clusters.
formula  used to generate the global profile-profile alignment is based on the posterior alignment probability matrices of the profiles.
in order to further improve the alignment accuracy, we then use a randomized iterative alignment to refine the initial alignment.
this randomized iterative refinement randomly partitions the given sequence group s into two separate groups, and performs a profile-profile alignment of the two groups.
the iterative refinement can be completed after  <dig> iterations by default, or a fixed number of iterations set by users.
generally speaking, the final progressive alignment orders sequences along the guide tree from closely related to distantly related.
to improve the alignment accuracy, a final iterative alignment is applied to refine the results from progressive alignment.
in addition, a multi-thread technology based on openmp is also used to improve the efficiency of the program  <cit> .
RESULTS
evaluation of msacompro and other tools on the standard benchmarks
we tested msacompro in comparison to three benchmarks: balibase, sabmark and oxbench, and evaluated the alignment results in terms of sum-of-pairs  score and true column  score.
the sp score is the number of correctly aligned pairs of residue in the test alignment divided by the total number of aligned pairs of residues in core blocks of the reference alignment  <cit> .
the tc score is the number of correctly aligned columns in the test alignment divided by the total number of aligned columns in core blocks of the reference alignment  <cit> .
we used the application bali_score provided by balibase  <dig>  to calculate these scores.
we compared msacompro to  <dig> other msa tools which do not have access to the structural information, including clustalw  <dig> .
<dig>  dialign-tx  <dig> .
<dig>  <cit> , fsa  <dig> .
<dig>  mafft  <dig> , msaprobs  <dig> .
<dig>  muscle  <dig> .
<dig>  opal  <dig> .
<dig>  poa  <dig>  probalign  <dig> , probcons and t-coffee  <dig> .
it is worth noting that a fair comparison between our method with these multiple sequence alignment methods without using structural features is not possible because these methods use less input information.
so, the goal of comparison is to present the idea that structural information-based alignment may contain valuable information that is not available in sequence-based multiple sequence alignments and can therefore be a supplement to sequence-based alignments.
and to make the evaluation more fair and comprehensive, we also compared msacompro with four tools which use structural information, including mummals  <dig>   <cit> , promals  <cit>  and promals3d  <cit> .
to understand how various parameters of msacompro affect alignment accuracy, some experiments were carried out to evaluate these variants based on two algorithm changes:  combining amino acids, secondary structure, and relative solvent accessibility information into the partition function calculation using respective weights for each of them;  computing the pairwise distance from both the pairwise posterior probability matrices and the pairwise contact map similarity matrices by introducing the weight wc for contact map information.
to optimize the parameters, we used balibase  <dig>  data sets as training sets, and sabmark  <dig>  and oxbench data sets as testing sets.
firstly, we focused on the effect of secondary structure and solvent accessibility information by testing different values of weight w <dig> for amino acid similarity and weight w <dig> for secondary structure information on balibase  <dig>  data sets.
msacompro worked wholly the best if the weight w <dig> for amino acid similarity and the weight w <dig> for secondary structure information were  <dig>  and  <dig> , respectively.
since the sum of w <dig>  w <dig> and wc is  <dig>  we can deduce that wc is  <dig>  if w <dig> and w <dig> are  <dig>  and  <dig> .
then we focused on the effect of residue-residue contact map information under two different scenarios: using secondary structure and relevant solvent accessibility information by keeping the w <dig>  w <dig>  and w <dig> at their optimum values , or excluding that information by setting both w <dig> and w <dig> as  <dig>  evaluation results on balibase  <dig>  database were found to improve the most when wc is  <dig>  by integrating both secondary structure and relevant solvent accessibility information.
additionally, to avoid over-fitting, we tested msacompro against sabmark  <dig>  and oxbench data sets using this set of parameters independently, and found that a significant improvement was also gained in comparison to other leading protein multiple sequence alignment tools.
more details can be found in the next section, "a comprehensive study on the effect of predicted structural information on the alignment accuracy".
consequently, the weights w <dig>  w <dig>  w <dig> and wc are respectively set at  <dig> ,  <dig> ,  <dig>  and  <dig>  in msacompro by default.
all other tools were also evaluated under default parameters.
firstly, we evaluated these methods on balibase  <cit>  - the most widely used multiple sequence alignment benchmark.
the latest version, balibase  <dig> , contains  <dig> reference alignments, which are distributed into five reference sets.
reference set  <dig> is a set of equal-distant sequences, which are organized into two reference subsets, rv <dig> and rv <dig>  rv <dig> contains sequences sharing >20% identity and rv <dig> contains sequences sharing 20% to 40% identity.
reference set  <dig> contains families with >40% identity and a significantly divergent orphan sequence that shares <20% identity with the rest of the family members.
reference set  <dig> contains families with >40% identity that share <20% identity between each two different sub-families.
reference set  <dig> is a set of sequences with large n/c-terminal extensions.
reference set  <dig> is a set of sequences with large internal insertions.
tables  <dig>   <dig>  and  <dig> report the mean sp scores and tc scores of msacompro and the tools without using structural information for the six subsets and the whole database.
all the scores in the tables are multiplied by  <dig>  and the highest scores in each column are marked in bold.
the results show that msacompro received the highest sp and tc scores on the whole database and all the subsets except for the sp score for the subset rv <dig>  in some cases, msacompro's improvement was substantial.
bold denotes the highest scores.
msacompro yielded the highest sp scores on all the subsets except rv <dig>  on some datasets such as rv <dig> and rv <dig>  the improvement is substantial.
bold denotes the highest scores.
msacompro yielded the highest tc scores on all the subsets.
bold denotes the highest scores.
msacompro has the highest mean sp and tc scores.
secondly, we evaluated msacompro and other tools without the help of structural information on the sabmark database  <cit> , which is a very challenging data set for multiple sequence alignment according to a comprehensive study  <cit> .
sabmark is an automatically generated data set consisting of two sets.
one set is from sofi  <cit>  and the other is from the astral database  <cit> , which contains remote homologous sequences in twilight-zone or superfamily.
since some pairwise reference alignments in sabmark are not generally consistent with multiple alignments, a subset of sabmark,  <dig>  called sabre  <cit> , has been widely used as a multiple sequence alignment benchmark database.
sabre was constructed by identifying mutually consistent columns  in the pairwise reference structure alignment.
mccs are considered similar to balibase core blocks.
sabre contains  <dig> out of  <dig> sabmark groups that have eight or more mccs.
table  <dig> shows the overall mean sp and tc scores of the alignments.
the mean sp and tc scores of msacompro are  <dig>  and  <dig>  points higher than those of the second best-performer, msaprobs, demonstrating that incorporating predicted structural features into multiple sequence alignments can substantially improve alignment accuracy for even remotely related homologous sequences.
figure  <dig> shows an example comparison between the alignments generated by our method, msacompro, and msaprobs from the sabre database.
the sp and tc scores significantly improved from  <dig>  to  <dig>  and  <dig> to  <dig> , respectively.
this case demonstrates that taking predicted structural information can help avert aligning unmatched regions, especially when the sequence similarity is unrecognizable.
bold denotes the highest scores.
the improvement of sp and tc scores on this data set is substantial.
thirdly, we also assessed all the tools without using the structural information on the oxbench database  <cit> .
oxbench is also a popular benchmark database generated by the amps multiple alignment method from the 3dee database of protein structural domains  <cit> .
the conserved columns in oxbench can be considered similar to balibase core blocks.
the mean sp and tc scores over the whole database are shown in table  <dig>  the results show that msacompro improves the alignment accuracy over all other methods.
finally, we also compared the sp scores and tc scores of msacompro and other tools which adopt the structural information on the six subsets of balibase database, sabmark database and oxbench database.
tables  <dig> and  <dig> demonstrate the sp and tc scores across the three databases.
the results show that msacompro gained the highest scores on three out of six subsets of balibase and achieved the third highest scores on other data sets, which are lower than promals3d that used true experimental structures as input and promals that used both predicted secondary structures and additional homologous protein sequences found by psi-blast search's on a large protein sequence database  <cit> .
overall, msacompro performed similarly as promals, whereas the latter has an advantage on a remote homologous protein sequence data set sabmark since it directly incorporates additional homologous protein sequences to improve the alignment of remotely related target sequences during the progressive alignment process.
moreover, the accuracy of msacompro on the balibase  <dig>  data sets seems to be higher than the published results of another alignment tool of using secondary structure information - dialign-sec  <cit> , which was not directly tested in our experiment because it is only available as a web server other than a downloadable software package.
therefore, msacompro is useful to improve the accuracy of multiple sequence alignment in general and particularly for most cases in reality where experimental structures are not available.
bold denotes the highest scores.
bold denotes the highest scores.
in order to check if alignment score differences between msacompro and the other alignment methods are statistically significant, we carried out the wilcoxon matched-pair signed-rank test  <cit>  on both sp and tc scores of these methods on the three data sets.
the p-values of alignment score differences calculated by the wilcoxon matched-pair signed-rank test are reported in table  <dig>  generally speaking, the alignment scores of msacompro are significantly higher than all the alignment methods without using structural information and mummals of using structural information in all but one case according to the significance threshold of  <dig> .
the exception is that msacompro's tc score is higher than msaprobs on the balibase, but not statistically significant.
however, the alignment scores of msacompro are mostly statistically lower than the other two alignment methods  of using predicted structural features, more homologous sequences, or tertiary structures.
the p-values were calculated using the wilcoxon matched-pair signed-rank test.
all the p-values except for ones denoted by "" are for hypothesis testing that msacompro has higher alignment scores than the other methods.
the p-values denoted by "" are for hypothesis testing that msacompro has lower alignment scores than the other methods.
in addition to alignment accuracy, alignment speed is also a factor to consider in time-critical applications.
because it is difficult to rigorously compare the speed of different methods due to the difference in implementation and inputs, we only report the roughly estimated running time of the different methods on balibase based our empirical observations.
the fastest methods are clustalw, mafft, muscle, and poa, which used less than one hour.
the medium-speed methods that used a few hours to less than one day include fsa, opal, probalign, msaprobs, probcons, t-coffee, mummals, and dialign-tx.
the more time demanding methods are msacompro, promals, and promals3d because they need to generate extra information for alignment.
we ran both promals and msacompro on the balibase  <dig>  database on an  <dig> eight-core  linux server to calculate their running time.
it took about  <dig> days and  <dig> hours for promals to run on the whole balibase  <dig>  data sets, and about  <dig> hours and  <dig> minutes for msacompro to run on the same data sets.
msacompro was faster because it used a multiple-threading implementation to call sspro/accpro to predict secondary structure and solvent accessibility in parallel.
out of about  <dig> hours and  <dig> minutes, about four hours and  <dig> minutes were used by msacompro to align sequences if secondary structure and solvent accessibility information was provided.
however, if only one cpu core is used, it took around  <dig> days and  <dig> hours for sspro and accpro called by msacompro to predict secondary structure and solvent accessibility information alone, which is time-consuming.
therefore, msacompro will be slower than promals if it runs a single cpu core, but faster on multiple  cpu cores.
as for promals3d, it used about  <dig> days to extract tertiary structure information and make alignments.
a comprehensive study of the effect of predicted structural information on the alignment accuracy
to understand the impact of predicted secondary structure, relative solvent accessibility, and contact map on the accuracy of multiple sequence alignment, we tested their effects on alignments individually or in combination by adjusting the values of their weights used in the partition function  or in the distance calculation .
i. effect of secondary structure information
we studied the effect of secondary structure information by adjusting the values of w <dig>  and w <dig> , the sum of which was kept as  <dig>  and setting the values of w <dig>  and wc  to  <dig>  the results for different w <dig> values on the sabmark data sets are shown in table  <dig>  the highest score is denoted in bold and by a superscript of star, and the second highest is denoted in bold.
the results show that incorporating secondary structure information always improves alignment accuracy over the baseline established without using secondary structure information .
the highest accuracy is achieved when w <dig> is set to .
<dig>  at which point the score is  <dig> points greater than the baseline.
w <dig> =  <dig> means that only secondary structure is used to calculate the posterior alignment probability in the partition function ), but amino acid sequence similarity is still used to calculate the other posterior alignment probability by the pair hidden markov models.
figures  <dig> and  <dig> plot the sp and tc scores against weight values in table  <dig> and table  <dig>  respectively.
the results show that using secondary structure information  always increases the alignment scores over without using it .
msacompro yielded the highest accuracy score of ~ <dig>  when w <dig> is set to  <dig> .
the results show that using secondary structure information  always increases the alignment scores over without using it .
msacompro yielded the highest accuracy score of ~ <dig>  when w <dig> is set to  <dig> .
ii.
effect of relative solvent accessibility information
similarly, we studied the effect of relative solvent accessibility on the sabmark by adjusting the values of w <dig> and w <dig> and setting the values of w <dig> and wc to  <dig>  the sp and tc scores with respect to different weight values are shown in tables  <dig> and  <dig>  respectively.
the scores are also plotted against the weights in figures  <dig> and  <dig>  respectively.
the highest sp and tc scores were achieved when w <dig> was set to  <dig>  or  <dig> .
the results show that using relative solvent accessibility information  always increases the alignment scores over without using it .
msacompro yielded the highest accuracy score of ~ <dig>  when w <dig> is set to  <dig> .
the results show that using relative solvent accessibility information  always increases the alignment scores over without using it .
msacompro yielded the highest accuracy score of ~ <dig>  when w <dig> is set to  <dig> .
iii.
effect of residue-residue contact map information
we investigated the effect of contact map information on the balibase  <dig>  data set by adjusting wc and setting w <dig> and w <dig> to  <dig>  we used nncon to successfully predict the contact maps for subset rv <dig>  rv <dig>   <dig> out of  <dig> alignments in rv <dig>   <dig> out of  <dig> in rv <dig>   <dig> out of  <dig> in rv <dig>  and  <dig> out of  <dig> in rv <dig>  we tested the msacompro method against this data with contact predictions.
tables  <dig> and  <dig> show the sp and tc scores for different wc values on the subsets of the balibase dataset.
the results show that using contact information improved the alignment accuracy on some, but not all, subsets.
iv.
effect of combining secondary structure and solvent accessibility information
we adjusted the values of w <dig> , w <dig>  and w <dig>  simultaneously to investigate the effect of using secondary structure and relative solvent accessibility together.
sp and tc scores on different parameter combinations are shown in tables  <dig> and  <dig>  the highest score is denoted in bold and by a superscript of  <dig>  the second in bold and by a superscript of  <dig>  and the third in bold and by a superscript of  <dig>  the results show that the highest scores are achieved when w <dig> ranges from  <dig>  to  <dig> , w <dig> from  <dig>  to  <dig> , and w <dig> from  <dig>  to  <dig> .
also, using both secondary structure and solvent accessibility improves alignment accuracy over using either one.
the best alignment score, which uses both secondary structure and solvent accessibility, is > <dig> points higher than the baseline approach, which does not use them.
the changes of sp scores and tc scores with respect to the weights are visualized by the 3d plots in figures  <dig> and  <dig>  we conducted similar experiments on balibase  <dig>  and oxbench and got the similar results .
bold denotes the top  <dig> highest scores.
the highest score is indicated by a superscript of  <dig>  the second highest by a superscript of  <dig>  and the third highest by a superscript of  <dig>  the table only shows the values of w <dig> and w <dig> because w <dig> can be inferred by  <dig> - w <dig> - w <dig>
bold denotes the top  <dig> highest scores.
the highest score is indicated by a superscript of  <dig>  the second highest by a superscript of  <dig>  and the third by a superscript of  <dig>  the table only shows the values of w <dig> and w <dig> because w <dig> can be inferred by  <dig> - w <dig> - w <dig>
v. effect of using contact map information together with secondary structure and solvent accessibility information
in order to study whether or not contact information can be used effectively with secondary structure and solvent accessibility, we adjusted the weight wc for contact information, while keeping the w <dig>  w <dig>  and w <dig> at their optimum values .
tables  <dig> and  <dig> report the sp and tc scores on the balibase  <dig>  data set for different wc values from no contact information  to maximum contact information .
the results show that the improvement caused by contact information seems not to be substantial and significant.
bold denotes the increased scores.
bold denotes the increased scores.
CONCLUSIONS
in this work, we designed a new method to incorporate predicted secondary structure, relative solvent accessibility, and residue-residue contact information into multiple protein sequence alignment.
our experiments on three standard benchmarks showed that the method improved multiple sequence alignment accuracy over most existing methods without using secondary structure and solvent accessibility information.
however, the performance of the method is comparable to promals and promals3d by slightly lower scores on some subsets and behind it by a large margin on sabmark probably because these two methods used homologous sequences or tertiary structure information in addition to secondary structure information.
since multiple sequence alignment is often a crucial step for bioinformatics analysis, this new method may help improve the solutions to many bioinformatics problems such as protein sequence analysis, protein structure prediction, protein function prediction, protein interaction analysis, protein mutagenesis and protein engineering.
authors' contributions
jc and xd designed the algorithm.
xd implemented the algorithm and carried out the experiments.
xd and jc analyzed the data.
xd and jc wrote the manuscript.
xd and jc approved it.

 aligning multiple evolutionarily related protein sequences is a fundamental technique for studying protein function, structure, and evolution. multiple sequence alignment methods are often an essential component for solving challenging bioinformatics problems such as protein function prediction, protein homology identification, protein structure prediction, protein interaction study, mutagenesis analysis, and phylogenetic tree construction. during the last thirty years or so, a number of methods and tools have been developed for multiple sequence alignment, which have made fundamental contributions to the development of the bioinformatics field. state of the art multiple sequence alignment methods adapt some popular techniques to improve alignment accuracy, such as iterative alignment, progressive alignment, alignment based on profile hidden markov models, and posterior alignment probability transformation. some alignment methods, such as 3d-coffee and promals3d, use 3d structure information to improve multiple sequence alignment, which cannot be applied to the majority of protein sequences without tertiary structures. in order to overcome this problem, we have developed a method to incorporate secondary structure, relative solvent accessibility, and contact map information predicted from protein sequences into multiple sequence alignment. predicted secondary structure information has been used to improve pairwise sequence alignment, but few attempts had been made to use predicted secondary structure information in multiple sequence alignment. to the best of our knowledge, applying predicted relative solvent accessibility and residue-residue contact map to multiple sequence alignment is novel. in order to use the predicted structural information to advance the state of the art of multiple sequence alignment, we first compared the existing multiple sequence alignment tools on the standard benchmark data sets such as balibase, sabmark and oxbench, which showed that mafft, t-coffee, msaprobs, and probcons yielded the best performance. then we developed msacompro, a new multiple sequence alignment method, which effectively utilizes predicted secondary structure, relative solvent accessibility, and residue-residue contact map together with posterior alignment probabilities produced by both pair hidden markov models and partition function as in msaprobs. the assessment results of msacompro compared to the benchmark data sets from balibase, sabmark and oxbench showed that incorporating predicted structural information has improved the accuracy of multiple sequence alignment over most existing tools without using structural features and sometimes the improvement is substantial. method following the general scheme in msaprobs, msacompro has five main steps: compute the pairwise posterior alignment probability matrices based on both pair-hmm and partition function, considering the similarity in amino acids, secondary structure, and relative solvent accessibility; generate the pairwise distance matrix from both the pairwise posterior probability matrices constructed in the first step and the pairwise contact map similarity matrices; construct a guide tree based on pairwise distance matrix, and calculate sequence weights; transform all the pairwise posterior matrices by a weighting scheme; perform a progressive alignment by computing the profile-profile alignment from the probability matrices of all sequence pairs, and then an iterative alignment to refine the results from progressive alignment. our method is different from msaprobs in that it adds secondary structure and solvent accessibility information to the calculation of the posterior residue-residue alignment probabilities and computes the pairwise distance matrix with the help of predicted residue-residue contact information. construction of pairwise posterior probability matrices based on amino acid sequence, secondary structure and solvent accessibility information for two protein sequences x and y in a sequence group s to be aligned, we denote x =, y =, where x x......, xn and y y......,yn are lists of the residues in x and y, respectively. n is the length of sequence x, and n is the length of sequence y. suppose xi is the i-th amino acid in sequence x, and yj is the j-th amino acid in sequence y. we let aln denote a global alignment between x and y, aln the set of of all the possible global alignments of x and y, and aln* ∈ aln the true pairwise alignment of x and y. the posterior probability that the i-th residue in x is aligned to the j-th residue in y in aln* is defined as: p=∑aln∈alnpi{xi~yj∈aln} i{xi~yj∈aln}={ iftrueo,otherwise p denotes the probability that aln is the true alignment aln*: thus, the posterior probability n × n matrix pxy is a collection of all the values p for short) for ≤ xi ≤ n ≤ yj ≤ n the calculation process of the pairwise posterior probability matrix is described as follows. as in msaprobs, two different methods are used to compute the pairwise posterior probability matrices, respectively. the first kind of pairwise probability matrix pxy is calculated by a partition function of alignments based on dynamic programming. f denotes the probability of all partial global alignments of x and y ending at position. fm is the probability of all partial global alignments with xi aligned to yj, fy, is the probability of all partial global alignments with yj aligned to a gap, and fx is the probability of all partial global alignments with xi aligned to a gap. accordingly, the partition function can be calculated recursively as follows: fm=few1βs+w2ss,ss)+w3sa,sa) fy=fmeβgap+fyeβext fx=fmeβgap+fxeβext f=fm+fy+fx subject to the constraint w + w + w = in the formula above, s is the amino acid similarity score between xi and yj. one element of the substitution matrix s, ss, ss) is the similarity score between the secondary structure ) of residue xi in protein x and that of residue yj in protein y according to the secondary structure similarity matrix ss, sa, sa) is the similarity score between the relative solvent accessibility ) of residue xi in protein x and that of residue yj in protein y according to the solvent accessibility similarity matrix sa. w w w are weights used to control the influence of the amino acid substitution score, secondary structure similarity score, and solvent accessibility similarity score. the secondary structure and solvent accessibility can be automatically predicted by sspro/accpro using a multi-threading technique implemented in msacompro, or alternatively be provided by a user. the values of the three weights are set to,, and by default, and can be adjusted by users. the ensembles of bidirectional recurrent neural network architectures in accpro are used to discriminate between two different states of relative solvent accessibility, higher or lower than the accessibility cutoff - 25% of the total surface area of a residue, corresponding to e or b. as in msaprobs, β is a parameter measuring the deviation between suboptimal and optimal alignments, gap is the gap open penalty, and ext is the gap extension penalty. we used the gonnet matrix as a substitution matrix to generate the similarity scores between two amino acids in proteins. the × secondary structure similarity matrix ss contains the similarity scores of three kinds of secondary structures as follows: ss=, where two identical secondary structures receive a score of and different ones receive a score of the × solvent accessibility similarity matrix sa contains the similarity scores of two kinds of relative solvent accessibilities as follows: sa=, where two identical solvent accessibilities receive a score of and different ones receive a it is worth noting that we used the simple identity scoring matrix for secondary structure and solvent accessibility here. employing more advance scoring matrices defined in may lead to further improvement. each posterior residue-residue alignment probability element in the first kind of posterior probability matrix can be calculated from the partition function as: p1=fmfm'f•ew1βs+w2ss,ss)+w3sa,sa), where fm′ denotes the partition function of all the reverse alignments starting from the position till position with xi aligned to yj. as in msaprobs, the second kind of pairwise probability matrix pxy is calculated by a pair hidden markov model combining both forward and backward algorithm. the pairwise probabilities can be generated under the guidance of pair hmm involving state emissions and transitions. pxy is only derived from protein sequences without using secondary structure and solvent accessibility, which is different from promals that lets hmm emit both amino acids and secondary structure alphabets. the final posterior probability matrix pxy is calculated as the root mean square of the corresponding values in pxy and pxy as follows. p=p12+p where p and p denote a posterior probability element in two kinds of posterior probability matrices, respectively. construction of pairwise distance matrices based on pairwise posterior probabilities and pairwise contact map scores the posterior probability matrix pxy is used as a scoring function to generate a pairwise global alignment between sequences x and y. the optimal global alignment score opt of the global alignment is computed according to an optimal sub-alignment score matrix as. the optimal sub-alignment score as denotes the score of the optimal sub-alignment ending at residues i and j in x and y. the as matrix is recursively calculated as: as=max{as+pxyasas as is the optimal score of the full global alignment between x and y, which is denoted as optscore. in addition to the optimal alignment score, we introduce a contact map score, cmscore, for the optimal pairwise alignment of x and y, assuming that the spatially neighboring residues of two aligned residues should have a higher tendency to be aligned together. cmscore is calculated from the contact map correlation score matrix cmapxy based on the residue-residue contact map matrices cmapx and cmapy of x and y. assuming the optimal global alignment of x and y is represented as, x1x......-xm......xp......xn1y1-......ykyk+....-......yn we can generate a new alignment after removing the pairs containing gaps: x......xm............xn1y.....yk+..........yn, which can be denoted as x1′x2′............xn′y1′y2′...........yn′, where n is the length of the new alignment without gaps from this alignment, we can construct two contact map matrices, cmapx and cmapy, shown below: cmapx=x11′x12′......x1n′x21′x22′......x2n′......................................xn1′xn2′......xnn′ cmapy=y11′y12′......y1n′y21′y22′......y2n′......................................yn1′yn2′......ynn′ xij′ is the contact probability score between amino acid xi′ and xj′ in protein sequence x, and yij′ is the contact probability score between amino acid yi' and yj' in protein sequence y. the residue-residue contact probabilities are predicted from the sequence by nncon. the contact map correlation score matrix cmapxy is calculated as the multiplication of cmapx and cmapy: cmapxy=cmapx×cmapy=xy11′xy12′....xy1n′xy21′xy22′....xy2n′............................................xyn1′xyn2′....xynn′ xyii′ is the contact map score for an aligned residue pair. the contact map score for the global alignment of two sequences x and y is calculated as cmscore=1n ∑i=1ncmapxy=1n ∑i=1nxyii′=1n ∑i=1n∑j=1nxij′yji′ in practice, we only need to calculate the diagonal values in cmapxy. finally, we define the pairwise distance between sequences x and y as d=1-w4optscoremin{n n2}-w5cmscore, where w + w = the weights w and w are used to control the influence of sequences x and y. construction of guide tree and transformation of posterior probability akin to msaprobs, a guide tree is constructed by the upgma method that uses the linear combinatorial strategy. the distance between a new cluster z formed by merging clusters x and y, and another cluster w is calculated as: d=d×num+d×numnum+num in which num is the number of leafs in cluster x. after the guide tree is constructed, sequences are weighted according to the schemes inferred in. to reduce the bias of sampling similar sequences, we use a weighted scheme to transform the former posterior probability as pxy′=1wnpxy+ ∑z∈s,z≠x,ywzpxzpzy) wx and wy are, respectively, the weight of sequences x and y, wz is the weight of a sequence z other than x or y in the given group of sequences, and wn is the sum of sequence weights in dataset s. combination of progressive and iterative alignment we first use the guide tree to generate a multiple sequence alignment by progressively aligning two clusters of the most similar sequences together. as in msaprobs, we also apply a weighted profile-profile alignment to align two clusters of sequences. the sequence weights are the same as in the previous step. the posterior alignment probability matrix of two clusters/profiles is averaged from the probability matrices of all sequence pairs, where x and y are from the two different clusters. formula used to generate the global profile-profile alignment is based on the posterior alignment probability matrices of the profiles. in order to further improve the alignment accuracy, we then use a randomized iterative alignment to refine the initial alignment. this randomized iterative refinement randomly partitions the given sequence group s into two separate groups, and performs a profile-profile alignment of the two groups. the iterative refinement can be completed after iterations by default, or a fixed number of iterations set by users. generally speaking, the final progressive alignment orders sequences along the guide tree from closely related to distantly related. to improve the alignment accuracy, a final iterative alignment is applied to refine the results from progressive alignment. in addition, a multi-thread technology based on openmp is also used to improve the efficiency of the program.  evaluation of msacompro and other tools on the standard benchmarks we tested msacompro in comparison to three benchmarks: balibase, sabmark and oxbench, and evaluated the alignment results in terms of sum-of-pairs score and true column score. the sp score is the number of correctly aligned pairs of residue in the test alignment divided by the total number of aligned pairs of residues in core blocks of the reference alignment. the tc score is the number of correctly aligned columns in the test alignment divided by the total number of aligned columns in core blocks of the reference alignment. we used the application bali_score provided by balibase to calculate these scores. we compared msacompro to other msa tools which do not have access to the structural information, including clustalw. dialign-tx., fsa. mafft, msaprobs. muscle. opal. poa probalign, probcons and t-coffee. it is worth noting that a fair comparison between our method with these multiple sequence alignment methods without using structural features is not possible because these methods use less input information. so, the goal of comparison is to present the idea that structural information-based alignment may contain valuable information that is not available in sequence-based multiple sequence alignments and can therefore be a supplement to sequence-based alignments. and to make the evaluation more fair and comprehensive, we also compared msacompro with four tools which use structural information, including mummals, promals and promals3d. to understand how various parameters of msacompro affect alignment accuracy, some experiments were carried out to evaluate these variants based on two algorithm changes: combining amino acids, secondary structure, and relative solvent accessibility information into the partition function calculation using respective weights for each of them; computing the pairwise distance from both the pairwise posterior probability matrices and the pairwise contact map similarity matrices by introducing the weight wc for contact map information. to optimize the parameters, we used balibase data sets as training sets, and sabmark and oxbench data sets as testing sets. firstly, we focused on the effect of secondary structure and solvent accessibility information by testing different values of weight w for amino acid similarity and weight w for secondary structure information on balibase data sets. msacompro worked wholly the best if the weight w for amino acid similarity and the weight w for secondary structure information were and, respectively. since the sum of w w and wc is we can deduce that wc is if w and w are and. then we focused on the effect of residue-residue contact map information under two different scenarios: using secondary structure and relevant solvent accessibility information by keeping the w w and w at their optimum values, or excluding that information by setting both w and w as evaluation results on balibase database were found to improve the most when wc is by integrating both secondary structure and relevant solvent accessibility information. additionally, to avoid over-fitting, we tested msacompro against sabmark and oxbench data sets using this set of parameters independently, and found that a significant improvement was also gained in comparison to other leading protein multiple sequence alignment tools. more details can be found in the next section, "a comprehensive study on the effect of predicted structural information on the alignment accuracy". consequently, the weights w w w and wc are respectively set at,, and in msacompro by default. all other tools were also evaluated under default parameters. firstly, we evaluated these methods on balibase - the most widely used multiple sequence alignment benchmark. the latest version, balibase, contains reference alignments, which are distributed into five reference sets. reference set is a set of equal-distant sequences, which are organized into two reference subsets, rv and rv rv contains sequences sharing >20% identity and rv contains sequences sharing 20% to 40% identity. reference set contains families with >40% identity and a significantly divergent orphan sequence that shares <20% identity with the rest of the family members. reference set contains families with >40% identity that share <20% identity between each two different sub-families. reference set is a set of sequences with large n/c-terminal extensions. reference set is a set of sequences with large internal insertions. tables and report the mean sp scores and tc scores of msacompro and the tools without using structural information for the six subsets and the whole database. all the scores in the tables are multiplied by and the highest scores in each column are marked in bold. the results show that msacompro received the highest sp and tc scores on the whole database and all the subsets except for the sp score for the subset rv in some cases, msacompro's improvement was substantial. bold denotes the highest scores. msacompro yielded the highest sp scores on all the subsets except rv on some datasets such as rv and rv the improvement is substantial. bold denotes the highest scores. msacompro yielded the highest tc scores on all the subsets. bold denotes the highest scores. msacompro has the highest mean sp and tc scores. secondly, we evaluated msacompro and other tools without the help of structural information on the sabmark database, which is a very challenging data set for multiple sequence alignment according to a comprehensive study. sabmark is an automatically generated data set consisting of two sets. one set is from sofi and the other is from the astral database, which contains remote homologous sequences in twilight-zone or superfamily. since some pairwise reference alignments in sabmark are not generally consistent with multiple alignments, a subset of sabmark, called sabre, has been widely used as a multiple sequence alignment benchmark database. sabre was constructed by identifying mutually consistent columns in the pairwise reference structure alignment. mccs are considered similar to balibase core blocks. sabre contains out of sabmark groups that have eight or more mccs. table shows the overall mean sp and tc scores of the alignments. the mean sp and tc scores of msacompro are and points higher than those of the second best-performer, msaprobs, demonstrating that incorporating predicted structural features into multiple sequence alignments can substantially improve alignment accuracy for even remotely related homologous sequences. figure shows an example comparison between the alignments generated by our method, msacompro, and msaprobs from the sabre database. the sp and tc scores significantly improved from to and to, respectively. this case demonstrates that taking predicted structural information can help avert aligning unmatched regions, especially when the sequence similarity is unrecognizable. bold denotes the highest scores. the improvement of sp and tc scores on this data set is substantial. thirdly, we also assessed all the tools without using the structural information on the oxbench database. oxbench is also a popular benchmark database generated by the amps multiple alignment method from the 3dee database of protein structural domains. the conserved columns in oxbench can be considered similar to balibase core blocks. the mean sp and tc scores over the whole database are shown in table the results show that msacompro improves the alignment accuracy over all other methods. finally, we also compared the sp scores and tc scores of msacompro and other tools which adopt the structural information on the six subsets of balibase database, sabmark database and oxbench database. tables and demonstrate the sp and tc scores across the three databases. the results show that msacompro gained the highest scores on three out of six subsets of balibase and achieved the third highest scores on other data sets, which are lower than promals3d that used true experimental structures as input and promals that used both predicted secondary structures and additional homologous protein sequences found by psi-blast search's on a large protein sequence database. overall, msacompro performed similarly as promals, whereas the latter has an advantage on a remote homologous protein sequence data set sabmark since it directly incorporates additional homologous protein sequences to improve the alignment of remotely related target sequences during the progressive alignment process. moreover, the accuracy of msacompro on the balibase data sets seems to be higher than the published results of another alignment tool of using secondary structure information - dialign-sec, which was not directly tested in our experiment because it is only available as a web server other than a downloadable software package. therefore, msacompro is useful to improve the accuracy of multiple sequence alignment in general and particularly for most cases in reality where experimental structures are not available. bold denotes the highest scores. bold denotes the highest scores. in order to check if alignment score differences between msacompro and the other alignment methods are statistically significant, we carried out the wilcoxon matched-pair signed-rank test on both sp and tc scores of these methods on the three data sets. the p-values of alignment score differences calculated by the wilcoxon matched-pair signed-rank test are reported in table generally speaking, the alignment scores of msacompro are significantly higher than all the alignment methods without using structural information and mummals of using structural information in all but one case according to the significance threshold of. the exception is that msacompro's tc score is higher than msaprobs on the balibase, but not statistically significant. however, the alignment scores of msacompro are mostly statistically lower than the other two alignment methods of using predicted structural features, more homologous sequences, or tertiary structures. the p-values were calculated using the wilcoxon matched-pair signed-rank test. all the p-values except for ones denoted by "" are for hypothesis testing that msacompro has higher alignment scores than the other methods. the p-values denoted by "" are for hypothesis testing that msacompro has lower alignment scores than the other methods. in addition to alignment accuracy, alignment speed is also a factor to consider in time-critical applications. because it is difficult to rigorously compare the speed of different methods due to the difference in implementation and inputs, we only report the roughly estimated running time of the different methods on balibase based our empirical observations. the fastest methods are clustalw, mafft, muscle, and poa, which used less than one hour. the medium-speed methods that used a few hours to less than one day include fsa, opal, probalign, msaprobs, probcons, t-coffee, mummals, and dialign-tx. the more time demanding methods are msacompro, promals, and promals3d because they need to generate extra information for alignment. we ran both promals and msacompro on the balibase database on an eight-core linux server to calculate their running time. it took about days and hours for promals to run on the whole balibase data sets, and about hours and minutes for msacompro to run on the same data sets. msacompro was faster because it used a multiple-threading implementation to call sspro/accpro to predict secondary structure and solvent accessibility in parallel. out of about hours and minutes, about four hours and minutes were used by msacompro to align sequences if secondary structure and solvent accessibility information was provided. however, if only one cpu core is used, it took around days and hours for sspro and accpro called by msacompro to predict secondary structure and solvent accessibility information alone, which is time-consuming. therefore, msacompro will be slower than promals if it runs a single cpu core, but faster on multiple cpu cores. as for promals3d, it used about days to extract tertiary structure information and make alignments. a comprehensive study of the effect of predicted structural information on the alignment accuracy to understand the impact of predicted secondary structure, relative solvent accessibility, and contact map on the accuracy of multiple sequence alignment, we tested their effects on alignments individually or in combination by adjusting the values of their weights used in the partition function or in the distance calculation. i. effect of secondary structure information we studied the effect of secondary structure information by adjusting the values of w and w, the sum of which was kept as and setting the values of w and wc to the results for different w values on the sabmark data sets are shown in table the highest score is denoted in bold and by a superscript of star, and the second highest is denoted in bold. the results show that incorporating secondary structure information always improves alignment accuracy over the baseline established without using secondary structure information. the highest accuracy is achieved when w is set to. at which point the score is points greater than the baseline. w = means that only secondary structure is used to calculate the posterior alignment probability in the partition function ), but amino acid sequence similarity is still used to calculate the other posterior alignment probability by the pair hidden markov models. figures and plot the sp and tc scores against weight values in table and table respectively. the results show that using secondary structure information always increases the alignment scores over without using it. msacompro yielded the highest accuracy score of ~ when w is set to. the results show that using secondary structure information always increases the alignment scores over without using it. msacompro yielded the highest accuracy score of ~ when w is set to. ii. effect of relative solvent accessibility information similarly, we studied the effect of relative solvent accessibility on the sabmark by adjusting the values of w and w and setting the values of w and wc to the sp and tc scores with respect to different weight values are shown in tables and respectively. the scores are also plotted against the weights in figures and respectively. the highest sp and tc scores were achieved when w was set to or. the results show that using relative solvent accessibility information always increases the alignment scores over without using it. msacompro yielded the highest accuracy score of ~ when w is set to. the results show that using relative solvent accessibility information always increases the alignment scores over without using it. msacompro yielded the highest accuracy score of ~ when w is set to. iii. effect of residue-residue contact map information we investigated the effect of contact map information on the balibase data set by adjusting wc and setting w and w to we used nncon to successfully predict the contact maps for subset rv rv out of alignments in rv out of in rv out of in rv and out of in rv we tested the msacompro method against this data with contact predictions. tables and show the sp and tc scores for different wc values on the subsets of the balibase dataset. the results show that using contact information improved the alignment accuracy on some, but not all, subsets. iv. effect of combining secondary structure and solvent accessibility information we adjusted the values of w, w and w simultaneously to investigate the effect of using secondary structure and relative solvent accessibility together. sp and tc scores on different parameter combinations are shown in tables and the highest score is denoted in bold and by a superscript of the second in bold and by a superscript of and the third in bold and by a superscript of the results show that the highest scores are achieved when w ranges from to, w from to, and w from to. also, using both secondary structure and solvent accessibility improves alignment accuracy over using either one. the best alignment score, which uses both secondary structure and solvent accessibility, is > points higher than the baseline approach, which does not use them. the changes of sp scores and tc scores with respect to the weights are visualized by the 3d plots in figures and we conducted similar experiments on balibase and oxbench and got the similar results. bold denotes the top highest scores. the highest score is indicated by a superscript of the second highest by a superscript of and the third highest by a superscript of the table only shows the values of w and w because w can be inferred by - w - w bold denotes the top highest scores. the highest score is indicated by a superscript of the second highest by a superscript of and the third by a superscript of the table only shows the values of w and w because w can be inferred by - w - w v. effect of using contact map information together with secondary structure and solvent accessibility information in order to study whether or not contact information can be used effectively with secondary structure and solvent accessibility, we adjusted the weight wc for contact information, while keeping the w w and w at their optimum values. tables and report the sp and tc scores on the balibase data set for different wc values from no contact information to maximum contact information. the results show that the improvement caused by contact information seems not to be substantial and significant. bold denotes the increased scores. bold denotes the increased scores.  in this work, we designed a new method to incorporate predicted secondary structure, relative solvent accessibility, and residue-residue contact information into multiple protein sequence alignment. our experiments on three standard benchmarks showed that the method improved multiple sequence alignment accuracy over most existing methods without using secondary structure and solvent accessibility information. however, the performance of the method is comparable to promals and promals3d by slightly lower scores on some subsets and behind it by a large margin on sabmark probably because these two methods used homologous sequences or tertiary structure information in addition to secondary structure information. since multiple sequence alignment is often a crucial step for bioinformatics analysis, this new method may help improve the solutions to many bioinformatics problems such as protein sequence analysis, protein structure prediction, protein function prediction, protein interaction analysis, protein mutagenesis and protein engineering. authors' contributions jc and xd designed the algorithm. xd implemented the algorithm and carried out the experiments. xd and jc analyzed the data. xd and jc wrote the manuscript. xd and jc approved it. 
to the best of our knowledge, applying predicted relative solvent accessibility and contact map to multiple sequence alignment is novel. we designed and developed a new method, msacompro, to synergistically incorporate predicted secondary structure, relative solvent accessibility, and residue-residue contact information into the currently most accurate posterior probability-based msa methods to improve the accuracy of multiple sequence alignments. the rigorous benchmarking of our method to the standard benchmarks clearly demonstrated that incorporating predicted protein structural information improves the multiple sequence alignment accuracy over the leading multiple protein sequence alignment tools without using this information, such as msaprobs, probcons, probalign, t-coffee, mafft and muscle. the method is different from the multiple sequence alignment methods that use the tertiary structure information of some sequences since the structural information of our method is fully predicted from sequences. msacompro is an efficient and reliable multiple protein sequence alignment tool that can effectively incorporate predicted protein structural information into multiple sequence alignment. multiple sequence alignment is a basic tool for bioinformatics research and analysis. therefore, improving the accuracy of multiple sequence alignment is important for advancing many bioinformatics fields. it has been used essentially in almost all bioinformatics tasks such as protein structure modeling, gene and protein function prediction, dna motif recognition, and phylogenetic analysis.
 multiple sequence alignment is a basic tool for bioinformatics research and analysis. it has been used essentially in almost all bioinformatics tasks such as protein structure modeling, gene and protein function prediction, dna motif recognition, and phylogenetic analysis. therefore, improving the accuracy of multiple sequence alignment is important for advancing many bioinformatics fields.  we designed and developed a new method, msacompro, to synergistically incorporate predicted secondary structure, relative solvent accessibility, and residue-residue contact information into the currently most accurate posterior probability-based msa methods to improve the accuracy of multiple sequence alignments. the method is different from the multiple sequence alignment methods that use the tertiary structure information of some sequences since the structural information of our method is fully predicted from sequences. to the best of our knowledge, applying predicted relative solvent accessibility and contact map to multiple sequence alignment is novel. the rigorous benchmarking of our method to the standard benchmarks clearly demonstrated that incorporating predicted protein structural information improves the multiple sequence alignment accuracy over the leading multiple protein sequence alignment tools without using this information, such as msaprobs, probcons, probalign, t-coffee, mafft and muscle. and the performance of the method is comparable to the state-of-the-art method promals of using structural features and additional homologous sequences by slightly lower scores.  msacompro is an efficient and reliable multiple protein sequence alignment tool that can effectively incorporate predicted protein structural information into multiple sequence alignment. the software is available at http://sysbio.rnet.missouri.edu/multicom_toolbox/. 