sequence alignment tools are essential to biological research [ see , e.g. ( 1 ) , for a survey of multiple sequence alignment methods ] . in addition
to merely the residues / nucleotides , biologists often possess more knowledge regarding function , structure or conserved patterns of the sequences to be analyzed .
it is generally desirable to have such information incorporated into an alignment procedure , so that the alignment result can be more biologically meaningful .
for example , functionally important sites are generally expected to be aligned together , but a typical alignment tool often fails to achieve this if the sequence similarity is low . imposing constraints representing such information
turns out to be an effective manner to incorporate biological knowledge into an alignment tool .
( 2 ) formulated the constrained multiple sequence alignment problem , where each constraint is a single residue / nucleotide .
they considered alignment of rnase sequences , which are known to have a sequence of conserved residues his ( h ) , lys ( k ) and his . using h , k ,
h as constraints , in the resulting constrained alignment each of these three residues can be found aligned together in a column of the alignment , appearing in the order as specified .
( 3 ) then proposed an improved algorithm for pairwise alignment and an approximation algorithm for multiple alignment .
it is also noted that there have been other formulations regarding alignment with constraints proposed from different perspectives with various approaches ( 414 ) .
conserved sites of a protein / rna / dna family are often of several residues / nucleotides long . for these patterns ,
15 ) proposed a generalized formulation and algorithm , where each constraint is a ( usually short ) string pattern allowing mismatches .
lu and huang ( 16 ) then proposed a space efficient algorithm for this formulation .
web - based systems , music ( 15 ) ( available at http://genome.life.nctu.edu.tw/music ) and music - me ( 16 ) ( available at http://genome.life.nctu.edu.tw/musicme ) , were also developed ; from now on these two systems will be referred to as music jointly . with the aid of music , tsai et al .
( 15 ) and lu and huang ( 16 ) successfully identified a fragment in the 3 untranslated region ( 3-utr ) of a sars ( severe acute respiratory syndrome ) coronavirus sequence that can fold into a pseudoknot , which is potentially responsible for self - replication of the virus . indeed ,
since its release , music has been found useful in , e.g. detection of functionally and/or structurally important residues / motifs in sequences ( 17,18 ) , prediction of rna pseudoknotted structures ( 15,19,20 ) , prediction of protein structures ( 21 ) and so on .
there are , however , formulations of many biologically significant patterns beyond the capability of music . for example
, many function - related protein sites as those collected in the prosite database ( 22 ) are expressed in regular expressions , which can not be modeled using the substring - with - mismatch formulation of constraints implemented in music .
an example of regular expression patterns is the egf - like domain signature 2 ( egf_2 , ps01186 in prosite ) : c - x - c - x(2)-[gp]-[fyw]-x(4,8)-c , which is related to the initiation of a signal transduction that results in dna synthesis and cell proliferation .
the meaning of this pattern is that , the first residue is cys , followed by one residue of any kind , then a cys , followed by two residues of any kind , then a gly or pro , etc .
regular expressions are also convenient in describing variable ranges between patterns or between blocks within a pattern , which is necessary for some single patterns themselves , and useful in applications where different patterns are expected to exhibit proximity in their occurrences . in the above example of egf_2 ,
the  x(4,8) symbol preceding the last cys indicates a range of length varying from 4 to 8 between a residue of [ f , y or w ] ( phe , tyr or trp ) and that last cys . due to the usefulness of regular expressions in describing biological patterns ,
an enhanced web server , re - music ( multiple sequence alignment with regular expression constraints ) , capable of handling regular expression constraints , is developed .
dialign ( 8,9,12,13 ) ( http://dialign.gobics.de/ ) is a well - known web server that can accept user - defined constraints as anchor points .
it can be noted that the constraint formulation of dialign and the one of re - music are significantly different . in dialign ,
a constraint consists of the exact positions of a pair of equal - length segments on two of the sequences , where these two segments are expected to be aligned together .
conflicts of constraints , if any , are resolved according to a weight function defined on the segment pairs .
each pattern may occur many times in a sequence , where each occurrence needs not have the same length .
the occurrences to be aligned together so as to satisfy the constraints will be those that can make the overall alignment optimized . re - music provides an intuitive user interface ( figure 1 ) .
the user enters or pastes the input sequences ( in fasta format ) in the largest blank field .
the format for the constraints follows the prosite pattern format ( please see the help page at http://140.113.239.131/re-music/help.html for details ) .
each constraint is put within quotes , and adjacent constraints are separated by space characters .
. the preferred scoring matrix may be chosen , and the gap open / extension penalties can be assigned .
the user can also enter an email address so that a hyperlink to the alignment result will be sent via email .
the output page shows the constrained alignment with the regions for the satisfactions of the constraints shaded in yellow ( figure 2b ) . on the output page
the user can also choose to download the alignment result in fasta format or clustalw format . 

another field with title  regular expression constraint(s) is for the user to enter the regular expression constraints , in a prosite - like format ( for details please refer to the help page at http://140.113.239.131/re-music/help.html ) . in this figure ,
( b ) a partial view of the alignment produced by re - music . a common pattern of these gst sequences , namely  [ st]-x(2)-[de] ( ps00006 ) , as obtained from prosite , is used as constraint . in the resulting alignment ,
re - music annotated the region for the satisfaction of the constraint with a yellow block .
it can be seen that the g - site residues are aligned properly , as desired . for both tools ,
another field with title  regular expression constraint(s) is for the user to enter the regular expression constraints , in a prosite - like format ( for details please refer to the help page at http://140.113.239.131/re-music/help.html ) . in this figure ,
( b ) a partial view of the alignment produced by re - music . a common pattern of these gst sequences , namely  [ st]-x(2)-[de] ( ps00006 ) , as obtained from prosite , is used as constraint . in the resulting alignment ,
re - music annotated the region for the satisfaction of the constraint with a yellow block .
it can be seen that the g - site residues are aligned properly , as desired .
sequence alignment tools are essential to biological research [ see , e.g. ( 1 ) , for a survey of multiple sequence alignment methods ] . in addition
to merely the residues / nucleotides , biologists often possess more knowledge regarding function , structure or conserved patterns of the sequences to be analyzed .
it is generally desirable to have such information incorporated into an alignment procedure , so that the alignment result can be more biologically meaningful .
for example , functionally important sites are generally expected to be aligned together , but a typical alignment tool often fails to achieve this if the sequence similarity is low . imposing constraints representing such information
turns out to be an effective manner to incorporate biological knowledge into an alignment tool .
( 2 ) formulated the constrained multiple sequence alignment problem , where each constraint is a single residue / nucleotide .
they considered alignment of rnase sequences , which are known to have a sequence of conserved residues his ( h ) , lys ( k ) and his . using h , k ,
h as constraints , in the resulting constrained alignment each of these three residues can be found aligned together in a column of the alignment , appearing in the order as specified .
( 3 ) then proposed an improved algorithm for pairwise alignment and an approximation algorithm for multiple alignment .
it is also noted that there have been other formulations regarding alignment with constraints proposed from different perspectives with various approaches ( 414 ) .
conserved sites of a protein / rna / dna family are often of several residues / nucleotides long . for these patterns ,
15 ) proposed a generalized formulation and algorithm , where each constraint is a ( usually short ) string pattern allowing mismatches .
lu and huang ( 16 ) then proposed a space efficient algorithm for this formulation .
web - based systems , music ( 15 ) ( available at http://genome.life.nctu.edu.tw/music ) and music - me ( 16 ) ( available at http://genome.life.nctu.edu.tw/musicme ) , were also developed ; from now on these two systems will be referred to as music jointly . with the aid of music , tsai et al .
( 15 ) and lu and huang ( 16 ) successfully identified a fragment in the 3 untranslated region ( 3-utr ) of a sars ( severe acute respiratory syndrome ) coronavirus sequence that can fold into a pseudoknot , which is potentially responsible for self - replication of the virus . indeed ,
since its release , music has been found useful in , e.g. detection of functionally and/or structurally important residues / motifs in sequences ( 17,18 ) , prediction of rna pseudoknotted structures ( 15,19,20 ) , prediction of protein structures ( 21 ) and so on .
there are , however , formulations of many biologically significant patterns beyond the capability of music . for example
, many function - related protein sites as those collected in the prosite database ( 22 ) are expressed in regular expressions , which can not be modeled using the substring - with - mismatch formulation of constraints implemented in music .
an example of regular expression patterns is the egf - like domain signature 2 ( egf_2 , ps01186 in prosite ) : c - x - c - x(2)-[gp]-[fyw]-x(4,8)-c , which is related to the initiation of a signal transduction that results in dna synthesis and cell proliferation .
the meaning of this pattern is that , the first residue is cys , followed by one residue of any kind , then a cys , followed by two residues of any kind , then a gly or pro , etc .
regular expressions are also convenient in describing variable ranges between patterns or between blocks within a pattern , which is necessary for some single patterns themselves , and useful in applications where different patterns are expected to exhibit proximity in their occurrences . in the above example of egf_2 ,
the  x(4,8) symbol preceding the last cys indicates a range of length varying from 4 to 8 between a residue of [ f , y or w ] ( phe , tyr or trp ) and that last cys . due to the usefulness of regular expressions in describing biological patterns ,
an enhanced web server , re - music ( multiple sequence alignment with regular expression constraints ) , capable of handling regular expression constraints , is developed .
dialign ( 8,9,12,13 ) ( http://dialign.gobics.de/ ) is a well - known web server that can accept user - defined constraints as anchor points .
it can be noted that the constraint formulation of dialign and the one of re - music are significantly different . in dialign ,
a constraint consists of the exact positions of a pair of equal - length segments on two of the sequences , where these two segments are expected to be aligned together .
conflicts of constraints , if any , are resolved according to a weight function defined on the segment pairs .
each pattern may occur many times in a sequence , where each occurrence needs not have the same length .
the occurrences to be aligned together so as to satisfy the constraints will be those that can make the overall alignment optimized .
re - music provides an intuitive user interface ( figure 1 ) . the user enters or pastes the input sequences ( in fasta format ) in the largest blank field .
the format for the constraints follows the prosite pattern format ( please see the help page at http://140.113.239.131/re-music/help.html for details ) .
each constraint is put within quotes , and adjacent constraints are separated by space characters .
. the preferred scoring matrix may be chosen , and the gap open / extension penalties can be assigned .
the user can also enter an email address so that a hyperlink to the alignment result will be sent via email .
the output page shows the constrained alignment with the regions for the satisfactions of the constraints shaded in yellow ( figure 2b ) . on the output page
the user can also choose to download the alignment result in fasta format or clustalw format . 

another field with title  regular expression constraint(s) is for the user to enter the regular expression constraints , in a prosite - like format ( for details please refer to the help page at http://140.113.239.131/re-music/help.html ) . in this figure ,
( b ) a partial view of the alignment produced by re - music . a common pattern of these gst sequences , namely  [ st]-x(2)-[de] ( ps00006 ) , as obtained from prosite , is used as constraint . in the resulting alignment ,
re - music annotated the region for the satisfaction of the constraint with a yellow block .
it can be seen that the g - site residues are aligned properly , as desired .
another field with title  regular expression constraint(s) is for the user to enter the regular expression constraints , in a prosite - like format ( for details please refer to the help page at http://140.113.239.131/re-music/help.html ) . in this figure ,
( b ) a partial view of the alignment produced by re - music . a common pattern of these gst sequences , namely  [ st]-x(2)-[de] ( ps00006 ) , as obtained from prosite , is used as constraint . in the resulting alignment ,
re - music annotated the region for the satisfaction of the constraint with a yellow block .
it can be seen that the g - site residues are aligned properly , as desired . for both tools ,
the regular expression constrained sequence alignment problem was originally formulated by arslan ( 23 ) .
the algorithm proposed in ( 23 ) is for pairwise alignment with a single constraint . in ( 24 ) arslan extended the algorithm in ( 23 ) to support multiple alignment with multiple constraints .
unfortunately , the time complexity is extremely high , involving an exponential multiplicative factor in addition to the exponential time complexity for optimal ( unconstrained ) msa computations .
even for pairwise alignment with multiple constraints , its worst case time and space requirements are intensive .
in addition , the algorithms in ( 23,24 ) can not find in the resulting alignment the regions responsible for the satisfactions of the constraints ; only the alignment score , without the alignment itself , is reported . but being able to report alignments is important for a web server .
it is therefore necessary to propose a solution more suitable for practical applications . for pairwise alignment with one regular expression constraint , in a previous study ( 25 )
we have proposed an algorithm , which is more efficient both in time and in space than the one in ( 23 ) .
furthermore , the alignment in addition to the score can be reconstructed without worsening the time and space complexity . in this work
we extend the algorithm in ( 25 ) to support multiple constraints and multiple sequences , as required in re - music .
the resulting algorithm is more efficient than the one in ( 24 ) for pairwise alignment with multiple constraints . to deal with multiple sequences ,
a progressive method is implemented , using our improved pairwise algorithm as the kernel . for details of the algorithm the reader
the glutathione binding site ( g - site ) on glutathione s - transferase ( gst ) had been found to have conserved architectures across species ( 26 ) .
the chemical natures of their residues acting as g - site ligands and interactions facilitated with glutathione are also analogous ( 26 ) . in a reasonable alignment of gst protein sequences ,
therefore , the residues for the g - site are expected to be aligned together .
a structural superposition of the crystal structures of gst proteins from different species also suggests that most of these g - site residues should be aligned together ( 26 ) .
the sequence identity of those gst proteins from different species , however , is quite low ; for example , it is reported in ( 26 ) that the pairwise sequence identity between the a. thaliana gst and each of other six non - plant gsts is no more than 20.2% .
in such a case , interfered by the low - similarity regions , it would be difficult for a typical alignment tool to align the important residues well .
an experiment is therefore undertaken to examine the performance of a typical alignment tool in this case , as well as to demonstrate how re - music can be used to produce a more reasonable alignment . in this experiment
we analyze three gst proteins : ( i ) atgst : a phi class gst from plant a. thaliana ( pdbid : 1gnw ) ; ( ii ) sjgst : an alpha class gst from non - mammalian s. japonicum ( flat worm ) ( pdbid : 1m99 ) ; ( iii ) ssgst : a pi class gst from mammalian s. scrofa ( pig ) ( pdbid : 2gsr ) .
the result is shown in figure 2a , where active site residues shared by these gsts are boxed .
it can be seen that , part of the g - site residues failed to be aligned together , due to the low sequence similarity among these gst proteins . by querying prosite with the three proteins , it is found that they all share the pattern ps00006 ( [ st]-x(2)-[de ] ) . using this pattern as constraint , re - music
these suggest that , with some information about common patterns , re - music is more reliable to produce alignments in which biologically important residues can be lined up , which is particularly important when the sequence identity is low .
being more reliable in aligning together important residues , re - music may also be applied to align an unknown sequence with other sequences whose relevant residues are known , thus providing a convenient and cheap way for a preliminary prediction of the residues in question on the unknown sequence .
note also that , in this experiment , the knowledge about the active site residues are not utilized in constructing the alignment ; the constraints do not involve the active site residues themselves .
such a property is useful when the residues to be predicted are not expected to be conserved in the sequence level .
there is considerable evidence that suggests phylogenetically conserved pseudoknots found in the 3-utrs of various coronaviruses are involved in rna replication of these viruses ( 28 ) . in an alignment of the 3-utr sequences of coronaviruses ,
however , it is often the case that the sequence identity among the coronaviruses from different groups is low .
it is not an easy task for a typical alignment tool to align together the conserved pseudoknots . in this experiment
four coronaviruses are considered in this experiment ( genbank accession numbers in parentheses ) : ( i ) hcov-229e : human 229e coronavirus ( af304460 ) , ( ii ) pedv : porcine epidemic diarrhea virus ( af353511 ) , ( iii ) bcov : bovine coronavirus ( af220295 ) and ( iv ) mhv : murine hepatitis virus ( af201929 ) .
the first two are group 1 coronaviruses , while the others belong to group 2 .
not surprisingly , since the sequence identity is low , the phylogenetically conserved pseudoknots ( shaded regions ) are not aligned well . in ( 28 ) , predicted secondary structures of the pseudoknots found in the 3-utr of various coronaviruses are given .
a consensus of the pseudoknots is to be taken . since , in general , loops in pseudoknots are less conserved , to enhance flexibility , we exclude loop regions nucleotides from the consensus .
then the consensus of the pseudoknots can be described as  x(5)-c - u - x(4)-c - x(15,16)-u - g - x(2)-a - x(5,7)-g - x(4)-a - g - x(7,10)-u - x(3)-a - x(5). using this consensus as the constraint , re - music is applied to align these 3-utr sequences again . in figure 3b
, the pseudoknot regions on these coronaviruses can be seen to have been aligned properly .
this demonstrates that re - music can be used to help locate fragments that are conserved in structure .
actually , this property , being a common advantage of the music series , had been utilized to predict the pseudoknot in the 3-utr of the sars - tw1 coronavirus by aligning the 3-utr of sars - tw1 with those of some other coronaviruses whose pseudoknot regions are known ( 15,16 ) .
re - music further makes it possible to provide the flexibility of variable ranges between conserved nucleotides or regions in constraints , which is necessary for describing the whole consensus of the pseudoknot in this experiment .
the shaded regions , corresponding to the phylogenetically conserved pseudoknots , are not aligned well .
as expected , the regions for the pseudoknots are aligned properly by re - music . for both tools ,
the shaded regions , corresponding to the phylogenetically conserved pseudoknots , are not aligned well .
as expected , the regions for the pseudoknots are aligned properly by re - music . for both tools ,
the glutathione binding site ( g - site ) on glutathione s - transferase ( gst ) had been found to have conserved architectures across species ( 26 ) .
the chemical natures of their residues acting as g - site ligands and interactions facilitated with glutathione are also analogous ( 26 ) . in a reasonable alignment of gst protein sequences ,
therefore , the residues for the g - site are expected to be aligned together .
a structural superposition of the crystal structures of gst proteins from different species also suggests that most of these g - site residues should be aligned together ( 26 ) .
the sequence identity of those gst proteins from different species , however , is quite low ; for example , it is reported in ( 26 ) that the pairwise sequence identity between the a. thaliana gst and each of other six non - plant gsts is no more than 20.2% .
in such a case , interfered by the low - similarity regions , it would be difficult for a typical alignment tool to align the important residues well .
an experiment is therefore undertaken to examine the performance of a typical alignment tool in this case , as well as to demonstrate how re - music can be used to produce a more reasonable alignment . in this experiment
we analyze three gst proteins : ( i ) atgst : a phi class gst from plant a. thaliana ( pdbid : 1gnw ) ; ( ii ) sjgst : an alpha class gst from non - mammalian s. japonicum ( flat worm ) ( pdbid : 1m99 ) ; ( iii ) ssgst : a pi class gst from mammalian s. scrofa ( pig ) ( pdbid : 2gsr ) .
the result is shown in figure 2a , where active site residues shared by these gsts are boxed .
it can be seen that , part of the g - site residues failed to be aligned together , due to the low sequence similarity among these gst proteins . by querying prosite with the three proteins , it is found that they all share the pattern ps00006 ( [ st]-x(2)-[de ] ) . using this pattern as constraint , re - music
these suggest that , with some information about common patterns , re - music is more reliable to produce alignments in which biologically important residues can be lined up , which is particularly important when the sequence identity is low .
being more reliable in aligning together important residues , re - music may also be applied to align an unknown sequence with other sequences whose relevant residues are known , thus providing a convenient and cheap way for a preliminary prediction of the residues in question on the unknown sequence .
note also that , in this experiment , the knowledge about the active site residues are not utilized in constructing the alignment ; the constraints do not involve the active site residues themselves .
such a property is useful when the residues to be predicted are not expected to be conserved in the sequence level .
there is considerable evidence that suggests phylogenetically conserved pseudoknots found in the 3-utrs of various coronaviruses are involved in rna replication of these viruses ( 28 ) . in an alignment of the 3-utr sequences of coronaviruses ,
however , it is often the case that the sequence identity among the coronaviruses from different groups is low .
it is not an easy task for a typical alignment tool to align together the conserved pseudoknots . in this experiment
four coronaviruses are considered in this experiment ( genbank accession numbers in parentheses ) : ( i ) hcov-229e : human 229e coronavirus ( af304460 ) , ( ii ) pedv : porcine epidemic diarrhea virus ( af353511 ) , ( iii ) bcov : bovine coronavirus ( af220295 ) and ( iv ) mhv : murine hepatitis virus ( af201929 ) .
the first two are group 1 coronaviruses , while the others belong to group 2 .
not surprisingly , since the sequence identity is low , the phylogenetically conserved pseudoknots ( shaded regions ) are not aligned well . in ( 28 ) , predicted secondary structures of the pseudoknots found in the 3-utr of various coronaviruses are given .
since , in general , loops in pseudoknots are less conserved , to enhance flexibility , we exclude loop regions nucleotides from the consensus . then the consensus of the pseudoknots can be described as  x(5)-c - u - x(4)-c - x(15,16)-u - g - x(2)-a - x(5,7)-g - x(4)-a - g - x(7,10)-u - x(3)-a - x(5). using this consensus as the constraint , re - music is applied to align these 3-utr sequences again . in figure 3b
, the pseudoknot regions on these coronaviruses can be seen to have been aligned properly .
this demonstrates that re - music can be used to help locate fragments that are conserved in structure .
actually , this property , being a common advantage of the music series , had been utilized to predict the pseudoknot in the 3-utr of the sars - tw1 coronavirus by aligning the 3-utr of sars - tw1 with those of some other coronaviruses whose pseudoknot regions are known ( 15,16 ) .
re - music further makes it possible to provide the flexibility of variable ranges between conserved nucleotides or regions in constraints , which is necessary for describing the whole consensus of the pseudoknot in this experiment .
( a ) a partial view of the alignment produced by clustalw . the shaded regions , corresponding to the phylogenetically conserved pseudoknots , are not aligned well .
as expected , the regions for the pseudoknots are aligned properly by re - music .
the shaded regions , corresponding to the phylogenetically conserved pseudoknots , are not aligned well .
as expected , the regions for the pseudoknots are aligned properly by re - music . for both tools ,
re - music adopts regular expressions as its constraint formulation , which is useful in expressing prosite patterns or structural elements that often involve variable ranges between conserved parts .
the algorithm underlying re - music represents an improvement over the previously proposed algorithm , and is more appropriate for implementation in a web - server .
experiments on gst proteins and on coronaviruses with phylogenetically conserved pseudoknots demonstrate that , with additional knowledge incorporated , re - music is able to produce meaningful alignments in which important residues or structural elements can be aligned properly , even if the similarity among input sequences is low .
 re - music is a web - based multiple sequence alignment tool that can incorporate biological knowledge about structure , function , or conserved patterns regarding the sequences of interest . 
 it accepts amino acid or nucleic acid sequences and a set of constraints as inputs . 
 the constraints are pattern descriptions , instead of exact positions of fragments to be aligned together . 
 the output is an alignment where for each pattern ( constraint ) , an occurrence on each sequence can be found aligned together with those on the other sequences , in a manner that the overall alignment is optimized . 
 its predecessor , music , has been found useful by researchers since its release in 2004 . 
 however , it is noticed in applications that the pattern formulation adopted in music , namely , plain strings allowing mismatches , is not expressive and flexible enough . 
 the constraint formulation adopted in re - music is therefore enhanced to be regular expressions , which is convenient in expressing many biologically significant patterns like those collected in the prosite database , or structural consensuses that often involve variable ranges between conserved parts . 
 experiments demonstrate that re - music can be used to help predict important residues and locate phylogenetically conserved structural elements . 
 re - music is available on - line at http://140.113.239.131/re-music . 
INTRODUCTION
Background and motivation
Using RE-MuSiC
METHODS
EXPERIMENTS
Protein sequences with active site residues
RNA sequences with phylogenetically conserved pseudoknots
SUMMARY