BACKGROUND
a multiple alignment of nucleotide or protein sequences often forms the basis for phylogenetic analysis.
in a perfect alignment, gaps correspond to insertion or deletion events, and as such should contain phylogenetic information on a par with substitutions.
while some work has been done to make use of this type of data  <cit>  there are still many unsolved issues.
additionally, gaps can also stem from misalignment, as well as from sequencing or data-management problems, in which case they obviously provide no useful information.
consequently, several bioinformatical and phylogenetic analyses are often based on alignments where gapped columns  have been discarded.
for instance, removal of gapped columns is an option in the frequently used programs paup  <cit> , paml  <cit>  and crann  <cit> .
however, as the number of sequences in an alignment grows, the probability of having a gap in any given site also grows, and with it the risk of removing that site from the analysis.
an alternative approach, that is sometimes used when applying maximum likelihood and other model-based methods, is to treat the gaps as unknown nucleotides  and sum over all the possible combinations, but this is not consensual and can become prohibitively costly for larger data sets.
for some bioinformatical analyses, moreover, this alternative is not possible.
one way around this problem is to remove particularly gap-rich sequences, thereby ending up with a dataset containing more ungapped columns.
this solution is of course not meaningful if the main goal of the analysis is to infer the topology of the phylogenetic tree connecting all the included taxa and one has a sufficiently long sequence.
however, there are many other scenarios where the approach can be useful.
for instance, it is often the case in molecular evolutionary analysis today that the focus is not on the phylogeny but on the analysis of the sequences themselves, and on properties of each position, such as the rate of evolution or the action of natural selection.
in such cases keeping the sites in the analysis becomes important.
the use of an automated, rapid alignment clean-up method is also clearly relevant in the case of large-scale or batch-type analyses, where phylogenies are produced from many potentially large data sets, or in the case of bioinformatical analyses not tolerant to the presence of gaps.
RESULTS
overview
the goal of this tool is to maximize the alignment area, defined as the number of characters that are present in gap free columns.
alignment area is thus equal to the number of sequences included in the alignment times the number of columns that have no gaps.
this maximization of the alignment area is done by selectively removing sequences from the alignment.
finding the right sequences to remove, however, is not a straightforward problem .
to scrutinize the performance of maxalign, we have analyzed very large sets of protein alignments from two different sources:  alignments extracted from the pfam database <cit> , and  synthetic alignments created by simulating evolution on a set of three different trees using the program simprot  <cit> .
the pfam data were chosen to be representative of typical, fairly diverged biological alignments, and consisted of all the  <dig> alignments from pfam-a, release  <dig> , that had between  <dig> and  <dig> sequences.
the simulated data were constructed so it resembled the pfam-data in terms of sequence divergence, and in the number and length of gaps .
specifically, we analyzed the following aspects of maxalign behaviour:  performance of the heuristic version of the maxalign algorithm ,  improvement of alignment area by maxalign,  ability of maxalign to remove "contaminating"  sequences from an alignment,  impact of maxalign on phylogenetic accuracy , and  impact of maxalign on the computation time of subsequent maximum likelihood phylogenetic analysis.
performance of maxalign heuristic algorithm
maxalign can use one of two different algorithms: a heuristic algorithm , and an optimal algorithm .
we tested both algorithms on the full pfam dataset.
the average runtime for the heuristic was  <dig>  seconds per alignment  demonstrating that use of maxalign is not a bottleneck for data analysis.
among the  <dig> alignments, the heuristic algorithm found the optimal solution in 78% of the alignments.
in only 4% of the alignments, the heuristic algorithm did not find the optimal solution.
the remaining alignments either could not be improved from the start , or the branch and bound algorithm could not reach a solution in  <dig> hours .
thus, the heuristic algorithm found the best solution in 95% of the cases in which a solution was found.
moreover, analysis of the solutions in the few cases where the heuristic was not optimal showed that the alignment area of the heuristic solution was, on average,  <dig> % of the optimal solution .
on the whole, we therefore recommend using the heuristic algorithm of maxalign.
improving the alignment area
the alignment area of the pfam alignments was quite variable, with a majority  having no gap free columns .
the average number of gap free columns in the unprocessed alignments was only  <dig> , and the average alignment area  <dig> .
the optimization of alignment area performed by maxalign resulted in a 10-fold increase to an average alignment area of  <dig>  corresponding to an 8-fold mean increase of  <dig>  gap free columns per alignment, at the average cost of only 19% of the sequences in the alignment.
in a small minority  of the  <dig> cases it was not possible to improve the alignment area by removing sequences, and maxalign therefore had no effect.
thus, the majority of pfam alignments were unusable for analyses requiring the elimination of gapped columns and became usable datasets by processing with maxalign.
average values for alignment dimensions before and after processing with maxalign.
estimated from  <dig> pfam alignments with between  <dig> and  <dig> sequences.
removing non-homologous sequences
it is not rare that data sets are contaminated with non-homologous sequences.
these will typically result in the generation of many gaps when the sequences are aligned.
to investigate how well maxalign performs in removal of such contaminating sequences we therefore constructed a set of noisy datasets: for each of the  <dig> original pfam alignments we added random, non-homologous sequences  such that the final content of noise was approximately 10%.
these datasets were then re-aligned using the program mafft with default parameters <cit> .
we then ran maxalign  on the resulting alignments and analyzed the performance in terms of removal of contaminating sequences.
we found that, taken over all  <dig> alignments, maxalign performed very well, removing on average 87% of the non-homologous sequences per alignment .
in 46% of all cases, maxalign was able to remove all non-homologous sequences from the alignment.
impact on phylogenetic analysis
accuracy
it is an unsolved issue in phylogenetic analysis how to best deal with gaps.
we touched upon this topic by investigating how maxalign and removal of gapped columns interfere with phylogenetic tree inference.
to do so, we first simulated  <dig> alignments along each of  <dig> trees of different shapes.
from each of these synthetic alignments, we then constructed three derived data sets by  removing gapped columns,  applying maxalign, and  applying maxalign and removing gapped columns.
for each of the resulting  <dig>  synthetic alignments , we then performed maximum likelihood phylogenetic analysis using the program phyml.
the accuracy of phylogenetic reconstruction was then analyzed by calculating the normalized symmetric tree similarity  between the true tree  on one hand, and the four trees estimated by phylogenetic analysis on the other.
these tree similarities were computed based on the subset of taxa shared by the original and maxaligned datasets.
for the trees inferred from the original  alignment and from the original alignment excluding gaps, we also computed the similarity to the true tree based on the full set of taxa.
the outcome of this comparison can be found both in figure  <dig> and table  <dig>
phylogenetic accuracy for datasets with/without removal of gapped columns, and processed/not processed by maxalign.
accuracy is measured as the average normalized symmetric tree similarity between the true tree  and the individual inferred trees, with the standard error of the mean  given in parenthesis.
"subset" refers to the set of taxa  common to the original and the maxaligned data.
"all" means all taxa in the original data set.
values marked with * are the only ones whose difference is not statistically significant.
when measuring phylogenetic accuracy on the subset of taxa that remain after maxalign processing, it can be seen that the highest phylogenetic accuracy was achieved by using all the sequences available without discarding gapped columns .
however, it can also be seen that applying maxalign decreases the accuracy only very slightly .
moreover, if one decides to discard columns with gaps, then using maxalign is clearly the best option .
if the accuracy of trees  is measured on the full set of taxa, then a different trend is apparent: especially in trees  <dig> and  <dig>  it can be seen that processing the alignment with maxalign increases the accuracy of the phylogeny .
the reason for this phenomenon is that maxalign predominantly removes sequences with many gaps.
these will necessarily also be the ones having the fewest amino acids, and therefore the ones associated with the highest phylogenetic uncertainty.
it is important to note that in phylogenetic analyses that measure support for each branch, such as bayesian analysis or bootstrap, the position of these taxa would show up with low support values.
it should also be noted that the presence of gaps in some sequences does not seem to disturb phylogenetic inference on the remaining sequences .
it should be noted that we have not investigated the additional impact of alignment error on this, since we directly use the simulated  alignments themselves.
computation time
one reason for discarding gapped columns is that summing over all possible missing values is a time consuming step in a maximum likelihood calculation.
we have evaluated how much time is saved by using maxalign with and without discarding columns with gaps.
the results are presented in table  <dig>
runtimes of the phylogenetic analysis.
all times measured in minutes.
both application of maxalign and removal of gapped columns resulted in strongly decreased runtimes.
it can be seen that either using maxalign or removing columns with gaps nearly halves the computer time needed to find the phylogenetic tree.
removing columns with gaps does so by preventing the summation over unknown characters as well as reducing the number of sites to be included in the analysis.
maxalign diminishes the number of summations required and also reduces the size of the dataset, by including fewer sequences.
the computer time required for these phylogenetic analyses was particularly short, as we used a very fast program , and the alignments contained few sequences.
in situations using more time-consuming analyses and software, as well as larger alignments, these relative differences in computing time will have an increased impact.
CONCLUSIONS
in the present work, we have shown how maxalign is helpful in "cleaning up" big alignments, and demonstrated how it may be used in connection with phylogenetic analysis.
in the analysis presented above, we found that the use of maxalign more than halved the running time of the analysis even when gapped columns were not excluded.
when gapped columns were discarded from the alignment, the output was of much higher quality if maxalign was first used to pre-process the data, as the number of columns included in the analysis increased immensely.
we have also shown that in the conditions tested, the accuracy of the phylogenetic estimate of the tree topology increases if one includes the gapped columns.
the sequences removed by maxalign were predominantly those associated with the highest degree of uncertainty regarding their placement in the final trees.
the use of maxalign prior to bioinformatical and phylogenetic analyses optimizes the number of nucleotides or amino acids present in ungapped alignment columns , thereby increasing the amount of useful data and/or the speed of the analysis.
moreover, maxalign is also very helpful in detecting misaligned or defective sequences without requiring manual inspection.
given its very short running times and ease of use, it can without difficulty be used as a step in both automated and manual phylogenetic and bioinformatical analyses.

 a multiple alignment of nucleotide or protein sequences often forms the basis for phylogenetic analysis. in a perfect alignment, gaps correspond to insertion or deletion events, and as such should contain phylogenetic information on a par with substitutions. while some work has been done to make use of this type of data there are still many unsolved issues. additionally, gaps can also stem from misalignment, as well as from sequencing or data-management problems, in which case they obviously provide no useful information. consequently, several bioinformatical and phylogenetic analyses are often based on alignments where gapped columns have been discarded. for instance, removal of gapped columns is an option in the frequently used programs paup, paml and crann. however, as the number of sequences in an alignment grows, the probability of having a gap in any given site also grows, and with it the risk of removing that site from the analysis. an alternative approach, that is sometimes used when applying maximum likelihood and other model-based methods, is to treat the gaps as unknown nucleotides and sum over all the possible combinations, but this is not consensual and can become prohibitively costly for larger data sets. for some bioinformatical analyses, moreover, this alternative is not possible. one way around this problem is to remove particularly gap-rich sequences, thereby ending up with a dataset containing more ungapped columns. this solution is of course not meaningful if the main goal of the analysis is to infer the topology of the phylogenetic tree connecting all the included taxa and one has a sufficiently long sequence. however, there are many other scenarios where the approach can be useful. for instance, it is often the case in molecular evolutionary analysis today that the focus is not on the phylogeny but on the analysis of the sequences themselves, and on properties of each position, such as the rate of evolution or the action of natural selection. in such cases keeping the sites in the analysis becomes important. the use of an automated, rapid alignment clean-up method is also clearly relevant in the case of large-scale or batch-type analyses, where phylogenies are produced from many potentially large data sets, or in the case of bioinformatical analyses not tolerant to the presence of gaps.  overview the goal of this tool is to maximize the alignment area, defined as the number of characters that are present in gap free columns. alignment area is thus equal to the number of sequences included in the alignment times the number of columns that have no gaps. this maximization of the alignment area is done by selectively removing sequences from the alignment. finding the right sequences to remove, however, is not a straightforward problem. to scrutinize the performance of maxalign, we have analyzed very large sets of protein alignments from two different sources: alignments extracted from the pfam database, and synthetic alignments created by simulating evolution on a set of three different trees using the program simprot. the pfam data were chosen to be representative of typical, fairly diverged biological alignments, and consisted of all the alignments from pfam-a, release, that had between and sequences. the simulated data were constructed so it resembled the pfam-data in terms of sequence divergence, and in the number and length of gaps. specifically, we analyzed the following aspects of maxalign behaviour: performance of the heuristic version of the maxalign algorithm, improvement of alignment area by maxalign, ability of maxalign to remove "contaminating" sequences from an alignment, impact of maxalign on phylogenetic accuracy, and impact of maxalign on the computation time of subsequent maximum likelihood phylogenetic analysis. performance of maxalign heuristic algorithm maxalign can use one of two different algorithms: a heuristic algorithm, and an optimal algorithm. we tested both algorithms on the full pfam dataset. the average runtime for the heuristic was seconds per alignment demonstrating that use of maxalign is not a bottleneck for data analysis. among the alignments, the heuristic algorithm found the optimal solution in 78% of the alignments. in only 4% of the alignments, the heuristic algorithm did not find the optimal solution. the remaining alignments either could not be improved from the start, or the branch and bound algorithm could not reach a solution in hours. thus, the heuristic algorithm found the best solution in 95% of the cases in which a solution was found. moreover, analysis of the solutions in the few cases where the heuristic was not optimal showed that the alignment area of the heuristic solution was, on average, % of the optimal solution. on the whole, we therefore recommend using the heuristic algorithm of maxalign. improving the alignment area the alignment area of the pfam alignments was quite variable, with a majority having no gap free columns. the average number of gap free columns in the unprocessed alignments was only, and the average alignment area. the optimization of alignment area performed by maxalign resulted in a 10-fold increase to an average alignment area of corresponding to an 8-fold mean increase of gap free columns per alignment, at the average cost of only 19% of the sequences in the alignment. in a small minority of the cases it was not possible to improve the alignment area by removing sequences, and maxalign therefore had no effect. thus, the majority of pfam alignments were unusable for analyses requiring the elimination of gapped columns and became usable datasets by processing with maxalign. average values for alignment dimensions before and after processing with maxalign. estimated from pfam alignments with between and sequences. removing non-homologous sequences it is not rare that data sets are contaminated with non-homologous sequences. these will typically result in the generation of many gaps when the sequences are aligned. to investigate how well maxalign performs in removal of such contaminating sequences we therefore constructed a set of noisy datasets: for each of the original pfam alignments we added random, non-homologous sequences such that the final content of noise was approximately 10%. these datasets were then re-aligned using the program mafft with default parameters. we then ran maxalign on the resulting alignments and analyzed the performance in terms of removal of contaminating sequences. we found that, taken over all alignments, maxalign performed very well, removing on average 87% of the non-homologous sequences per alignment. in 46% of all cases, maxalign was able to remove all non-homologous sequences from the alignment. impact on phylogenetic analysis accuracy it is an unsolved issue in phylogenetic analysis how to best deal with gaps. we touched upon this topic by investigating how maxalign and removal of gapped columns interfere with phylogenetic tree inference. to do so, we first simulated alignments along each of trees of different shapes. from each of these synthetic alignments, we then constructed three derived data sets by removing gapped columns, applying maxalign, and applying maxalign and removing gapped columns. for each of the resulting synthetic alignments, we then performed maximum likelihood phylogenetic analysis using the program phyml. the accuracy of phylogenetic reconstruction was then analyzed by calculating the normalized symmetric tree similarity between the true tree on one hand, and the four trees estimated by phylogenetic analysis on the other. these tree similarities were computed based on the subset of taxa shared by the original and maxaligned datasets. for the trees inferred from the original alignment and from the original alignment excluding gaps, we also computed the similarity to the true tree based on the full set of taxa. the outcome of this comparison can be found both in figure and table phylogenetic accuracy for datasets with/without removal of gapped columns, and processed/not processed by maxalign. accuracy is measured as the average normalized symmetric tree similarity between the true tree and the individual inferred trees, with the standard error of the mean given in parenthesis. "subset" refers to the set of taxa common to the original and the maxaligned data. "all" means all taxa in the original data set. values marked with * are the only ones whose difference is not statistically significant. when measuring phylogenetic accuracy on the subset of taxa that remain after maxalign processing, it can be seen that the highest phylogenetic accuracy was achieved by using all the sequences available without discarding gapped columns. however, it can also be seen that applying maxalign decreases the accuracy only very slightly. moreover, if one decides to discard columns with gaps, then using maxalign is clearly the best option. if the accuracy of trees is measured on the full set of taxa, then a different trend is apparent: especially in trees and it can be seen that processing the alignment with maxalign increases the accuracy of the phylogeny. the reason for this phenomenon is that maxalign predominantly removes sequences with many gaps. these will necessarily also be the ones having the fewest amino acids, and therefore the ones associated with the highest phylogenetic uncertainty. it is important to note that in phylogenetic analyses that measure support for each branch, such as bayesian analysis or bootstrap, the position of these taxa would show up with low support values. it should also be noted that the presence of gaps in some sequences does not seem to disturb phylogenetic inference on the remaining sequences. it should be noted that we have not investigated the additional impact of alignment error on this, since we directly use the simulated alignments themselves. computation time one reason for discarding gapped columns is that summing over all possible missing values is a time consuming step in a maximum likelihood calculation. we have evaluated how much time is saved by using maxalign with and without discarding columns with gaps. the results are presented in table runtimes of the phylogenetic analysis. all times measured in minutes. both application of maxalign and removal of gapped columns resulted in strongly decreased runtimes. it can be seen that either using maxalign or removing columns with gaps nearly halves the computer time needed to find the phylogenetic tree. removing columns with gaps does so by preventing the summation over unknown characters as well as reducing the number of sites to be included in the analysis. maxalign diminishes the number of summations required and also reduces the size of the dataset, by including fewer sequences. the computer time required for these phylogenetic analyses was particularly short, as we used a very fast program, and the alignments contained few sequences. in situations using more time-consuming analyses and software, as well as larger alignments, these relative differences in computing time will have an increased impact.  in the present work, we have shown how maxalign is helpful in "cleaning up" big alignments, and demonstrated how it may be used in connection with phylogenetic analysis. in the analysis presented above, we found that the use of maxalign more than halved the running time of the analysis even when gapped columns were not excluded. when gapped columns were discarded from the alignment, the output was of much higher quality if maxalign was first used to pre-process the data, as the number of columns included in the analysis increased immensely. we have also shown that in the conditions tested, the accuracy of the phylogenetic estimate of the tree topology increases if one includes the gapped columns. the sequences removed by maxalign were predominantly those associated with the highest degree of uncertainty regarding their placement in the final trees. the use of maxalign prior to bioinformatical and phylogenetic analyses optimizes the number of nucleotides or amino acids present in ungapped alignment columns, thereby increasing the amount of useful data and/or the speed of the analysis. moreover, maxalign is also very helpful in detecting misaligned or defective sequences without requiring manual inspection. given its very short running times and ease of use, it can without difficulty be used as a step in both automated and manual phylogenetic and bioinformatical analyses. 
maxalign can be used prior to phylogenetic and bioinformatical analyses as well as in other situations where this form of alignment improvement is useful. we also show that it is not advisable to exclude gapped columns from phylogenetic analyses unless maxalign is used first. we demonstrate how maxalign is helpful in detecting misaligned or defective sequences without requiring manual inspection. the presence of gaps in an alignment of nucleotide or protein sequences is often an inconvenience for bioinformatical studies.
 the presence of gaps in an alignment of nucleotide or protein sequences is often an inconvenience for bioinformatical studies. in phylogenetic and other analyses, for instance, gapped columns are often discarded entirely from the alignment.  maxalign is a program that optimizes the alignment prior to such analyses. specifically, it maximizes the number of nucleotide symbols that are present in gap-free columns – the alignment area – by selecting the optimal subset of sequences to exclude from the alignment. maxalign can be used prior to phylogenetic and bioinformatical analyses as well as in other situations where this form of alignment improvement is useful. in this work we test maxalign's performance in these tasks and compare the accuracy of phylogenetic estimates including and excluding gapped columns from the analysis, with and without processing with maxalign. in this paper we also introduce a new simple measure of tree similarity, normalized symmetric similarity that we consider useful for comparing tree topologies.  we demonstrate how maxalign is helpful in detecting misaligned or defective sequences without requiring manual inspection. we also show that it is not advisable to exclude gapped columns from phylogenetic analyses unless maxalign is used first. finally, we find that the sequences removed by maxalign from an alignment tend to be those that would otherwise be associated with low phylogenetic accuracy, and that the presence of gaps in any given sequence does not seem to disturb the phylogenetic estimates of other sequences. the maxalign web-server is freely available online at http://www.cbs.dtu.dk/services/maxalign where supplementary information can also be found. the program is also freely available as a perl stand-alone package. 