building accurate multiple sequence alignments ( msas ) is one of the cornerstones of computational biology , as judged by the number of citations collected by msa publications over the last 30 years ( 1 ) .
one of the most important developments in msa methods over these last 10 years has been the introduction of the concept of template - based msas .
template - based msas make it possible to enrich the sequences one wishes to align with selected information .
the first reports of template - based alignments describe the use of structural templates associated with the sequences of interest ( 2,3 ) .
consistency - based methods provide an ideal framework for such template based analysis and over the years , novel data sources have been turned into sequence templates , including rna secondary structures ( 4 ) and profiles ( 5 ) using a procedure known as homology extension ( 6 ) .
although several reports suggest a significant increase in accuracy when using homology extension , this approach has seen its systematic usage limited by an often prohibitive computational cost and relatively complex deployment that requires tight integration between the aligner , blast and the databases .
we introduce here a new web server designed to provide users with a very efficient implementation of homology extension .
this server features the t - coffee homology extension procedure for both regular proteins ( position specific iterative t - coffee , psi - coffee ) ( 7 ) and transmembrane proteins ( tm - coffee ) ( 8) .
homology extension strategies use database searches to collect homologous sequences and generate a representative sequence profile for each input sequence .
relative to the individual sequences the profiles are enriched with evolutionary information , thus allowing informative position - specific scoring schemes to be derived for each sequence .
therefore , the use of profiles can achieve reasonable accurate alignments for highly divergent sequences ( i.e. balibase rv11 data set < 25% sequence identity ) without the use of structural information ( 7 ) . the notion of homology extension
was initially pioneered in promals-3d ( 9 ) and was also developed in a slightly different way in the praline series ( 9,10 ) .
none of these associated analyses did , however , explore the consequence of database redundancy levels when doing homology extension and the first analysis of this type was published in ( 8) showing that low redundancy databases allow very fast homology extension at a limited cost in terms of accuracy . for transmembrane proteins ( tmps ) ,
the databases available for homology searching within the web server range from uniref50 ( fast / rough ) to the full uniref100 non - redundant set ( slow / accurate ) . to the best of our knowledge
this is the only web server offering users the choice of the databases against which homology extension is to be carried out .
the web server addresses an important need in the community by providing an accessible method for performing homology extension - based alignments .
our benchmarking on the balibase2-ref7 -helical tmps shows a significant improvement over the most accurate methods ( 8) . in these benchmark reports
, we show that our approach outperforms the most accurate alternative procedures ( msaprobs , kalign , promals , mafft , probcons and praline ) while carrying out significantly faster homology extension thanks to the use of non - redundant databases . by using reduced databases containing only transmembrane annotated proteins
, tm - coffee is a specific alignment procedure for tmps that obtains similar results at a significantly reduced computational cost over full protein databases .
tm - coffee also incorporates transmembrane topology prediction using generated blast profiles as input to the hmmtop package ( hidden markov model for topolgy prediction ) ( 11 ) .
hmmtop utilizes a previously trained hidden markov model to classify the amino acid distribution in localized protein segments ( 12 ) .
tm - coffee maps these predictions back to the input sequences . both the homology extension and transmembrane topology prediction
are implemented in the web server , as well as in the t - coffee package ( 13 ) .
the hmmtop predictions do not contribute to the alignment procedure and are merely a post - processing prediction meant to yield a more informative output .
psi / tm - coffee incorporates homology information into t - coffee library construction . in t - coffee ,
a library is a collection of paired residues , as obtained in an all - against - all comparison of all the sequences within the dataset .
this library is used to derive a position - specific scoring scheme through a process known as extension during which the cost for matching two residues is set by combining the score of all the residue pairs supporting a triplet linking these two residues ( i.e. pair x - z and pair z - y to support matching x - y where x , y and z are three residues from three different sequences ) . of course , the higher the accuracy of the pairwise alignments used to populate the library , the higher the expected accuracy . in this respect ,
the main strength of t - coffee is its capacity to incorporate pairs from various sources . in psi / tm - coffee these pairs
are obtained through the profile comparison we described in the next paragraph and therefore are more likely to be correct .
the extended library scoring scheme is used by t - coffee in the same way as a standard scoring scheme used in a progressive alignment while sequences are being incorporated following the guide tree order . in order to achieve this
, the first computational step is homology extension where individual sequences are replaced with a set of multiply aligned homologs .
the purpose of homology extension is to reveal the evolutionary variability associated with each site of the considered sequences thus producing a more accurate t - coffee library for the alignment stage .
this procedure involves performing blast ( blast+ version 2.2.25 ) for each query sequence against the selected database .
the default database is uniref50 , a non - redundant database derived from uniprot where no two sequences have an identity > 50% . for transmembrane inputs ,
unirefxx - tm is an even smaller database produced by filtering the corresponding uniref dataset with the query string :  keyword : transmembrane. these tmp - specific databases are typically 80% smaller than the database they are extracted from .
the server uses static databases ( uniprot release 2011_02 ) , so as to insure stability with respect to the original tm - coffee publication ( 8) . at this point
, it is not entirely clear how regular updates should be so as to yield a positive impact on accuracy .
we therefore intend to keep this database static , using it in a way somehow similar to a substitution matrix ( i.e. pam or blosum matrices are not updated on larger datasets ) .
we nonetheless intend to monitor accuracy variation with newer database versions and will eventually proceed to regular updates if this proves suitable . blast hits with an identity level between 50 and 90% and a coverage higher than 70% with respect to the query sequence are kept .
the blast alignments of these hits are then stacked onto the query sequence , thus generating a one to all msa .
template profile in the  result files section ) by removing all columns corresponding to positions unaligned to the query ( i.e. gaps in the query ) and by filling unmatched query positions with gaps . a t - coffee library
is then produced by aligning every pair of profiles with a pair - hmm adapted from the probcons method ( 14 ) in order to deal with profiles .
the parameters and biphasic gap penalties ( two distinct sets of gap opening and extension penalties for short and longer gaps ) are the same as described by the probcons authors . every pair of matched columns with a posterior probability of being aligned higher than 0.99 are included into the library . in this procedure
, the matching cost of a pair of profile sequences is set to the average cost measured on the vectorized columns , as described in ( 15 ) .
this library of potential matching pairs across the considered sequences is eventually fed to the t - coffee consistency progressive alignment algorithm .
t - coffee uses its standard heuristic approach in an attempt to deliver an msa having the highest possible level of consistency with the library .
when the tmp toggle is checked , the transmembrane topology of each sequence will be predicted by hmmtop using its associated profile ( * .tmp ,  template protein transmembrane topology in the  result files section ) .
this extra prediction procedure is only used for display purposes ( see next  output section ) and is not required by the alignment procedure .
the psi / tm - coffee web server is part of the t - coffee web platform ; its access is free and unrestricted , without login procedure .
the server is accessible from http://tcoffee.crg.cat/tmcoffee with any standard web browser ( mozilla firefox 5 + , google chrome , internet explorer 8 + , safari 6 + and opera 11 + ) .
all the functions of the server are also available through the command line version of the t - coffee available at http://tcoffee.crg.cat/. detailed documentation for the t - coffee package is available at www.tcoffee.org ( http://www.tcoffee.org/projects/tcoffee/#documentation ) .
sequences can be input via the input field or alternatively provided using the upload link .
when the transmembrane toggle button is checked , the source databases will be further reduced by only keeping transmembrane - annotated entries .
these tmp - specific databases are 80% smaller than their sources ( 8) . besides performing alignment
the output will be tm_html instead of score_html ( see more details in the  output interpretation section ) .
the homology extension databases available are : 
 uniref50 , very fast , rough ( default ) : built by clustering uniref100 sequences at the 50% sequence identity level ( 16).uniref90 , fast , approximate : built by clustering uniref100 sequences at the 90% sequence identity level.uniref100 , slow , accurate : combines identical sequences and sub - fragments from any source organism into a single uniref entry ( i.e. cluster ) .
uniref50 , very fast , rough ( default ) : built by clustering uniref100 sequences at the 50% sequence identity level ( 16 ) .
uniref90 , fast , approximate : built by clustering uniref100 sequences at the 90% sequence identity level .
uniref100 , slow , accurate : combines identical sequences and sub - fragments from any source organism into a single uniref entry ( i.e. cluster ) .
the server performs a blast search for each query sequence against the selected database and turns the blast outputs into a profile that is used to produce the t - coffee library .
computation time is highly dependent on the number of sequences and the chosen homology extension database . for regular proteins , aligning 10 sequences using uniref50 takes 5 min on the web server whilst 200 sequences with the same database takes 2 h ( table 1 ) . in comparison , aligning the same 10 sequences using the full uniref 100 database takes 20 min ( table 2 ) .
when the tmp toggle is selected , the profile is utilized to predict tmps topology by hmmtop . whilst the database blast step is more efficient using the reduced transmembrane only databases , the topology prediction step adds to the computation cost . during and after the computation
, job details and results can be retrieved using the permanent url http://tcoffee.crg.cat/apps/tcoffee/result?rid=jobid , where jobid is the i d given at the time of submission . the server history is also kept in a cookie on the user 's browser enabling it to be accessed at any moment using the history link on the main menu .
the final output page contains a graphical version of the msa ( figure 1a ) , the raw result files , run parameters , citations and links for forwarding the results to other online tools .
the format of outputs presented is dependent on whether the transmembrane mode was activated and any advanced output options .
( a ) the graphical msa output coloured according to transmembrane topology prediction where yellow residues are predicted to be in the inner loop , red in the transmembrane helix and blue in the outer loop .
( b ) 3d structure of pdb i d : 2ziy with the hmmtop predicted transmembrane topology colouring .
the result page contains the following sections : 
 msa : the msa is coloured according to the t - coffee tcs scheme ( 19 ) .
dark pink blocks are very reliable , while blue and green bits are unreliable based on the t - coffee library .
the colour scheme has been designed to be easily visualized by colour - blind people.citation : the article for citing psi / tm - coffee.result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html is the html format of the above msa section and its plain text format , score_ascii.template list is the list of the homology profiles for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure .
msa : the msa is coloured according to the t - coffee tcs scheme ( 19 ) .
dark pink blocks are very reliable , while blue and green bits are unreliable based on the t - coffee library .
the colour scheme has been designed to be easily visualized by colour - blind people .
result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html is the html format of the above msa section and its plain text format , score_ascii.template list is the list of the homology profiles for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure .
score_html is the html format of the above msa section and its plain text format , score_ascii .
template profile contains the homology profile of each sequence from the blast search procedure . for tmps
the result page contains the following sections : 
 msa : the msa coloured according to transmembrane topology prediction by hmmtop ( 11 ) , where yellow is in loop , red is tm helix and blue is out loop ( figure 1a).citation : the article for citing psi / tm - coffee.result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
tm_html the html format of the above msa section indicates the transmembrane topology prediction.template list contains the list of homology profiles and topology predictions for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure.template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop .
msa : the msa coloured according to transmembrane topology prediction by hmmtop ( 11 ) , where yellow is in loop , red is tm helix and blue is out loop ( figure 1a ) .
result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats . score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
tm_html the html format of the above msa section indicates the transmembrane topology prediction.template list contains the list of homology profiles and topology predictions for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure.template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop .
score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
template list contains the list of homology profiles and topology predictions for the input sequences .
template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop . for both modes ,
all files ( figure 1c ) can be downloaded as a single zip file , copied to the user 's dropbox account or forwarded to other online tools for downstream visualization and analysis .
the info panel provides information such as elapsed time and a replay function allows re - running of the job with modifications to input options and data .
sequences can be input via the input field or alternatively provided using the upload link .
when the transmembrane toggle button is checked , the source databases will be further reduced by only keeping transmembrane - annotated entries .
these tmp - specific databases are 80% smaller than their sources ( 8) . besides performing alignment
the output will be tm_html instead of score_html ( see more details in the  output interpretation section ) .
the homology extension databases available are : 
 uniref50 , very fast , rough ( default ) : built by clustering uniref100 sequences at the 50% sequence identity level ( 16).uniref90 , fast , approximate : built by clustering uniref100 sequences at the 90% sequence identity level.uniref100 , slow , accurate : combines identical sequences and sub - fragments from any source organism into a single uniref entry ( i.e. cluster ) .
uniref50 , very fast , rough ( default ) : built by clustering uniref100 sequences at the 50% sequence identity level ( 16 ) .
uniref90 , fast , approximate : built by clustering uniref100 sequences at the 90% sequence identity level .
uniref100 , slow , accurate : combines identical sequences and sub - fragments from any source organism into a single uniref entry ( i.e. cluster ) .
the server performs a blast search for each query sequence against the selected database and turns the blast outputs into a profile that is used to produce the t - coffee library .
computation time is highly dependent on the number of sequences and the chosen homology extension database . for regular proteins , aligning 10 sequences using uniref50 takes 5 min on the web server whilst 200 sequences with the same database takes 2 h ( table 1 ) . in comparison , aligning the same 10 sequences using the full uniref 100 database takes 20 min ( table 2 ) .
when the tmp toggle is selected , the profile is utilized to predict tmps topology by hmmtop . whilst the database blast step is more efficient using the reduced transmembrane only databases , the topology prediction step adds to the computation cost . during and after the computation ,
job details and results can be retrieved using the permanent url http://tcoffee.crg.cat/apps/tcoffee/result?rid=jobid , where jobid is the i d given at the time of submission . the server history is also kept in a cookie on the user 's browser enabling it to be accessed at any moment using the history link on the main menu .
the final output page contains a graphical version of the msa ( figure 1a ) , the raw result files , run parameters , citations and links for forwarding the results to other online tools .
the format of outputs presented is dependent on whether the transmembrane mode was activated and any advanced output options .
( a ) the graphical msa output coloured according to transmembrane topology prediction where yellow residues are predicted to be in the inner loop , red in the transmembrane helix and blue in the outer loop .
( b ) 3d structure of pdb i d : 2ziy with the hmmtop predicted transmembrane topology colouring .
the result page contains the following sections : 
 msa : the msa is coloured according to the t - coffee tcs scheme ( 19 ) .
dark pink blocks are very reliable , while blue and green bits are unreliable based on the t - coffee library .
the colour scheme has been designed to be easily visualized by colour - blind people.citation : the article for citing psi / tm - coffee.result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html is the html format of the above msa section and its plain text format , score_ascii.template list is the list of the homology profiles for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure .
msa : the msa is coloured according to the t - coffee tcs scheme ( 19 ) .
dark pink blocks are very reliable , while blue and green bits are unreliable based on the t - coffee library .
the colour scheme has been designed to be easily visualized by colour - blind people .
result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html is the html format of the above msa section and its plain text format , score_ascii.template list is the list of the homology profiles for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure .
score_html is the html format of the above msa section and its plain text format , score_ascii .
template profile contains the homology profile of each sequence from the blast search procedure . for tmps
the result page contains the following sections : 
 msa : the msa coloured according to transmembrane topology prediction by hmmtop ( 11 ) , where yellow is in loop , red is tm helix and blue is out loop ( figure 1a).citation : the article for citing psi / tm - coffee.result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats .
score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
tm_html the html format of the above msa section indicates the transmembrane topology prediction.template list contains the list of homology profiles and topology predictions for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure.template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop .
msa : the msa coloured according to transmembrane topology prediction by hmmtop ( 11 ) , where yellow is in loop , red is tm helix and blue is out loop ( figure 1a ) .
result files : 
 tree is the guide tree used during the alignment procedure.multiple alignment subsection provides the msas in clustal , fasta and phylip formats . score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
tm_html the html format of the above msa section indicates the transmembrane topology prediction.template list contains the list of homology profiles and topology predictions for the input sequences.template profile contains the homology profile of each sequence from the blast search procedure.template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop .
score_html the html format of the t - coffee tcs score and its plain text format , score_ascii .
tm_html the html format of the above msa section indicates the transmembrane topology prediction . template list contains the list of homology profiles and topology predictions for the input sequences .
template protein transmembrane topology is the transmembrane topology prediction of each sequence , where i is in loop , h is tm helix and o is out loop . for both modes ,
all files ( figure 1c ) can be downloaded as a single zip file , copied to the user 's dropbox account or forwarded to other online tools for downstream visualization and analysis .
the info panel provides information such as elapsed time and a replay function allows re - running of the job with modifications to input options and data .
here we describe the psi / tm - coffee web server , a tool for performing homology extension based msas . as far as we know , the web server is the only online tool allowing for the choice of different homology extension databases .
the inclusion of specific transmembrane databases reduces the overall computational time and automated topology predictions give users a highly relevant and useful annotation ( figure 1b ) .
future updates will involve an on the fly computation of suitable nr databases using pfam as a starting point to select the most suitable sequence sets .
, p.d . ] ; center for genomic regulation ( crg ) ;  fundaci obra social la caixa ( to e.w.f , m.c ) ; spanish ministry of economy and competitiveness ,  centro de excelencia severo ochoa 20132017 [ sev-20120208 ] ; center for genomic regulation ( crg ) .
funding for open access charge : the open access publication charge for this paper has been waived by oxford university press - nar .
 the psi / tm - coffee web server performs multiple sequence alignment ( msa ) of proteins by combining homology extension with a consistency based alignment approach . 
 homology extension is performed with position specific iterative ( psi ) blast searches against a choice of redundant and non - redundant databases . 
 the main novelty of this server is to allow databases of reduced complexity to rapidly perform homology extension . 
 this server also gives the possibility to use transmembrane proteins ( tmps ) reference databases to allow even faster homology extension on this important category of proteins . 
 aside from an msa , the server also outputs topological prediction of tmps using the hmmtop algorithm . 
 previous benchmarking of the method has shown this approach outperforms the most accurate alignment methods such as msaprobs , kalign , promals , mafft , probcons and praline. the web server is available at http://tcoffee.crg.cat/tmcoffee . 
INTRODUCTION
ALGORITHM
PSI/TM-COFFEE WEB SERVER
Input
Computation
Output
DISCUSSION
FUNDING