tiling arrays are also gaining popularity for detecting novel transcripts in sequenced genomes . in this
context , sequence annotation is an essential step in understanding the genome and the transcriptome of a species .
large - scale comparisons of prokaryotic and eukaryotic genomes reveal thousands of conserved regions obtained by homology or synteny . these regions might be protein - coding sequences ( 1 ) or non - coding rna genes ( 2,3,4 ) . annotation by comparative analysis typically involves two steps : first aligning the sequences , then analysing the multiple alignment to detect an evolutionary pattern that is representative of the selection pressure .
this idea is exploited in exoniphy ( 5 ) for exon detection , in rnaz ( 6 ) or evofold ( 7 ) for structural rna prediction or in qrna ( 8) , that implements both a coding and an non - coding model for rnas . in this computational protocol
this task , however , is difficult because sequence similarity is often reduced at the nucleic level .
regarding protein coding genes , nucleic acid sequences exhibit a much larger sequence heterogeneity compared to their encoded amino acid sequences due to the redundancy of the genetic code .
it is well known that the combination of nucleic acid and amino acid sequence information leads to improved alignments ( 9,10 ) .
so pure - sequence - based multiple alignment tools perform poorly on low - homology datasets of structural rnas ( 11 ) . in this article , we present the magnolia website , whose objective is to provide an advanced tool for aligning nucleic acid sequences .
the idea is to get rid of the dichotomy between aligning and predicting the function .
if we assume that sequences are either protein - coding or structural rnas , it is possible to incorporate some functional information into the alignment algorithm to improve the result .
the multiple alignment can then be used as a starting point to refine the comparative analysis or to carry out further predictions , such as motif finding or phylogeny reconstruction .
first , it tries to predict the function of the sequences according to the substitution pattern between sequences .
second , a multiple alignment is built based on the putative function of the sequences .
if the sequences are recognized as coding sequences , then the multiple alignment uses the amino acid sequences .
if the sequences are recognized to contain a conserved secondary structure , then the mutiple alignment takes into consideration long - range base pair interactions .
magnolia includes three specific modules : protea for protein coding sequences , carnac and gardenia for structural rnas .
here the idea is that the selection pressure tends to preserve the encoded amino acid sequence , and it is possible to identifies coding sequences by looking for a global conservation of common reading frames .
the method first identifies best potential reading frames from each pair of sequences , and then incorporates this information into a frame graph from which a coding significancy score is calculated . by doing so
, it also predicts the associated reading frame for each sequence . if the sequences are classified as protein - coding sequences , then the multiple alignment of nucleic acid sequences is built from the hypothetical amino acid sequences using clustalw ( 13 ) , dialign2 ( 10 ) or t - coffee ( 14 ) .
, the selection pressure tends to preserve the secondary structure of the molecule , and mutations should retain the ability to form base pairs into energetically favorable stems .
carnac is able to recover a conserved secondary structure from a set of unaligned sequences .
( 16,17 ) , that fold and align several sequences at the same time , for example .
the algorithm uses a sankoff - based dynamic programing approach to identify conserved strutures for all pairs of sequences .
then all pairwise foldings are combined into a graph - theoretical structure called the stem graph . only frequent common stems that correspond to highly connected subgraphs in the stem graph are retained .
the method takes into account both the nucleic sequence and the putative common secondary structure predicted by carnac .
it relies on the dynamic programming algorithm for pairwise comparison proposed in ref . ( 18 ) .
rna sequences are encoded as arc - annotated sequences , and a multiple alignment for a set of arc - annotated sequences is a nested common supersequence .
the edit scheme incorporates evolutionary operations concerning free bases ( base substitution , base deletion ) and base pairs ( arc - mismatch , arc - removing , arc - breaking , arc - altering ) , originally defined in ref .
the method starts with constructing all pairwise alignments to determine the degree of similarity for each pair of sequences .
pairwise alignment of supersequences rely on the same algorithm as pairwise alignments for arc - annotated sequences .
this is made possible because supersequences can be viewed as a nested arc - annotated sequences on an extended alphabet .
the score of one node is its sp ( sum - of - pairs ) score .
lastly , the space search of the dynamic programming alignment is pruned using constraints coming from the carnac output .
magnolia requires as input data a set of rna or dna sequences in the standard fasta format .
it can be stored in a file to be uploaded to the server , or pasted directly in the text box .
the job assigned a unique identifier that can be used to retrieve results for one week .
if input sequences are annotated as coding sequences , then two multiple alignments are displayed . the first alignment is built on the putative amino acid sequences obtained by virtual translation using the predicted reading frame , and the second alignment is the corresponding alignment on nucleic acid sequences obtained by reverse translation , allowing for frameshifts .
codons in the nucleic acid sequences are put in color : two base triplets coding for the same amino acid bear the same color .
figure 2 shows an example of magnolia output obtained with a family of protein - coding sequences . 

if input sequences are annotated as structural rna genes , then a multiple alignment taking into consideration the primary structure accompanied by the secondary structure is displayed . concerning the secondary structure ,
base pairings are indicated in bracket - dot format : each base - pair is represented by a pair of matching brackets and unpaired bases are represented by dots .
the lack of pseudoknots in the secondary structure ensures that this notation defines a unique folding .
figure 3 shows an example of output obtained with a family of non - coding rnas . for each sequence , the individual putative secondary structure
is also provided in five formats : ct , jpeg , ps , bracket - dot format and as a list of constrained base pairings .
jpeg and ps files are automatically produced from the ct file using the naview layout program ( 22 ) . 

all pairings are correct , and the multiple alignment is consistent with the reference alignment available in rfam - rf00005 ( 21 ) .
all pairings are correct , and the multiple alignment is consistent with the reference alignment available in rfam - rf00005 ( 21 ) .
some data sets are not identified as coding rnas nor as non - coding rnas .
the first possibility is that the sequences might have an alternative function , such as untranslated regions in messenger rnas , promoter elements , etc .
the evolutionary signal is too weak and the sequences do not exhibit any significant mutational bias towards any model .
this limitation is harmless for practical purposes , because standard multiple sequence alignment tools usually yield good results on high - identity data sets .
so when the average identity percentage is greater than 90% , the server outputs a warning message and provides a default multiple alignment constructed directly with clustalw on the initial data set .
two such examples are the cis - acting regulatory element from the human rhinoviruses , that is located in the open reading frame of the capsid proteins [ rfam  rf00220 ( 21 ) ] , or the hepatitis c stem - loop vii structure found in the coding region of the rna - dependent rna polymerase gene ns5b [ rfam  rf000468 ( 21 ) ] .
magnolia requires as input data a set of rna or dna sequences in the standard fasta format .
it can be stored in a file to be uploaded to the server , or pasted directly in the text box .
the job assigned a unique identifier that can be used to retrieve results for one week .
if input sequences are annotated as coding sequences , then two multiple alignments are displayed .
the first alignment is built on the putative amino acid sequences obtained by virtual translation using the predicted reading frame , and the second alignment is the corresponding alignment on nucleic acid sequences obtained by reverse translation , allowing for frameshifts .
codons in the nucleic acid sequences are put in color : two base triplets coding for the same amino acid bear the same color .
figure 2 shows an example of magnolia output obtained with a family of protein - coding sequences . 

if input sequences are annotated as structural rna genes , then a multiple alignment taking into consideration the primary structure accompanied by the secondary structure is displayed .
concerning the secondary structure , base pairings are indicated in bracket - dot format : each base - pair is represented by a pair of matching brackets and unpaired bases are represented by dots .
the lack of pseudoknots in the secondary structure ensures that this notation defines a unique folding .
figure 3 shows an example of output obtained with a family of non - coding rnas .
for each sequence , the individual putative secondary structure is also provided in five formats : ct , jpeg , ps , bracket - dot format and as a list of constrained base pairings .
jpeg and ps files are automatically produced from the ct file using the naview layout program ( 22 ) . 

all pairings are correct , and the multiple alignment is consistent with the reference alignment available in rfam - rf00005 ( 21 ) .
all pairings are correct , and the multiple alignment is consistent with the reference alignment available in rfam - rf00005 ( 21 ) .
some data sets are not identified as coding rnas nor as non - coding rnas .
the first possibility is that the sequences might have an alternative function , such as untranslated regions in messenger rnas , promoter elements , etc .
the evolutionary signal is too weak and the sequences do not exhibit any significant mutational bias towards any model .
but this limitation is harmless for practical purposes , because standard multiple sequence alignment tools usually yield good results on high - identity data sets .
so when the average identity percentage is greater than 90% , the server outputs a warning message and provides a default multiple alignment constructed directly with clustalw on the initial data set .
two such examples are the cis - acting regulatory element from the human rhinoviruses , that is located in the open reading frame of the capsid proteins [ rfam  rf00220 ( 21 ) ] , or the hepatitis c stem - loop vii structure found in the coding region of the rna - dependent rna polymerase gene ns5b [ rfam  rf000468 ( 21 ) ] . in such cases , magnolia releases two multiple alignments .
we evaluate the accuracy of the method on two large data sets : pandit ( 20 ) and bralibase ii ( 11 ) .
pandit is a registry of families of homologous protein domains , accompanied by curated rna sequence alignments .
bralibase ii is a set of non - coding rna families that has been used to establish a benchmark of multiple sequence alignment programs upon structural rnas .
it is composed of four families : group ii introns , 5s rrna , trna and u5 spliceosomal rna . for each family
6122 ( 94.3% ) families are correctly classified as coding sequences , among them more than 99% with the correct reading frame predicted for each sequence .
less than 3% of the families are classified as structural rna . to estimate the quality of the alignments
, we used the sum - of - pairs score ( sps ) of the baliscore software ( 23 ) .
the sps is calculated such that it increases with the number of sequences correctly aligned .
we compared magnolia with clustalw , t - coffee and dialign2 on the same nucleic acid sequences .
the x - axis represents the average identity percentage and the y - axis represents the sps value . for magnolia , we tried all possible combinations concerning the alignment tool in the amino acid alignment step : clustalw , t - coffee and dialign2 . for dialign2
, we selected the appropriate option translation of nucleotide diagonals into peptide diagonals when comparing the nucleic acid sequences .
the x - axis represents the average identity percentage and the y - axis represents the sps value . for magnolia , we tried all possible combinations concerning the alignment tool in the amino acid alignment step : clustalw , t - coffee and dialign2 . for dialign2 , we selected the appropriate option translation of nucleotide diagonals into peptide diagonals when comparing the nucleic acid sequences .
this benchmark contains 388 alignments , that are classified into high , medium and low identity data sets .
magnolia failed to identify a structural evolutionary pattern for 20% of them and falsely assigned a protein coding function for 7% of them .
following ref . ( 11 ) , we use the structure conservation index ( sci ) to assess the accuracy of alignments .
this score provides a measure of the conserved secondary structure information contained within the alignment .
results for magnolia are reported in figure 5 , together with results for other alignment tools used in the benchmark .
we also evaluated the accuracy of the secondary structure found by magnolia and compared it to two recent structural alignment programs : murlet ( 16 ) and mlocarna ( 17 ) . for each software and for each identity class , we computed the percentage of correct base pairings amongst the set of predicted base pairings .
furthermore , the total runtime is more than 12 times faster for magnolia than for the two other methods ( < 20 min for the whole data set , compared to more than 4 hours ) . 

the x - axis represents the average identity percentage and the y - axis represents the sci value .
magnolia appears to be the closest curve to the reference curve for identity percentage ranging from 40% to 80% . for higher identity percentages ,
table 1.accuracy percentage for magnolia , murlet and mlocarna for reference secondary structures of bralibase iiidentity classlowmediumhighmagnolia72.0%76.3%87.0%murlet78.1%76.2%77.8%mlocarna68%71.1%78.9% magnolia alignments on bralibase ii .
the x - axis represents the average identity percentage and the y - axis represents the sci value .
magnolia appears to be the closest curve to the reference curve for identity percentage ranging from 40% to 80% . for higher identity percentages ,
6122 ( 94.3% ) families are correctly classified as coding sequences , among them more than 99% with the correct reading frame predicted for each sequence .
less than 3% of the families are classified as structural rna . to estimate the quality of the alignments
, we used the sum - of - pairs score ( sps ) of the baliscore software ( 23 ) .
the sps is calculated such that it increases with the number of sequences correctly aligned .
we compared magnolia with clustalw , t - coffee and dialign2 on the same nucleic acid sequences .
the x - axis represents the average identity percentage and the y - axis represents the sps value . for magnolia , we tried all possible combinations concerning the alignment tool in the amino acid alignment step : clustalw , t - coffee and dialign2 . for dialign2
, we selected the appropriate option translation of nucleotide diagonals into peptide diagonals when comparing the nucleic acid sequences .
the x - axis represents the average identity percentage and the y - axis represents the sps value . for magnolia , we tried all possible combinations concerning the alignment tool in the amino acid alignment step : clustalw , t - coffee and dialign2 . for dialign2
, we selected the appropriate option translation of nucleotide diagonals into peptide diagonals when comparing the nucleic acid sequences .
this benchmark contains 388 alignments , that are classified into high , medium and low identity data sets .
magnolia failed to identify a structural evolutionary pattern for 20% of them and falsely assigned a protein coding function for 7% of them .
following ref . ( 11 ) , we use the structure conservation index ( sci ) to assess the accuracy of alignments .
this score provides a measure of the conserved secondary structure information contained within the alignment .
results for magnolia are reported in figure 5 , together with results for other alignment tools used in the benchmark .
we also evaluated the accuracy of the secondary structure found by magnolia and compared it to two recent structural alignment programs : murlet ( 16 ) and mlocarna ( 17 ) . for each software and for each identity class , we computed the percentage of correct base pairings amongst the set of predicted base pairings .
furthermore , the total runtime is more than 12 times faster for magnolia than for the two other methods ( < 20 min for the whole data set , compared to more than 4 hours ) . 

the x - axis represents the average identity percentage and the y - axis represents the sci value .
magnolia appears to be the closest curve to the reference curve for identity percentage ranging from 40% to 80% . for higher identity percentages ,
table 1.accuracy percentage for magnolia , murlet and mlocarna for reference secondary structures of bralibase iiidentity classlowmediumhighmagnolia72.0%76.3%87.0%murlet78.1%76.2%77.8%mlocarna68%71.1%78.9% magnolia alignments on bralibase ii .
the x - axis represents the average identity percentage and the y - axis represents the sci value .
magnolia appears to be the closest curve to the reference curve for identity percentage ranging from 40% to 80% . for higher identity percentages ,
 magnolia is a new software for multiple alignment of nucleic acid sequences , which are recognized to be hard to align . 
 the idea is that the multiple alignment process should be improved by taking into account the putative function of the sequences . in this perspective 
 , magnolia is especially designed for sequences that are intended to be either protein - coding or structural rnas . 
 it extracts information from the similarities and differences in the data , and searches for a specific evolutionary pattern between sequences before aligning them . 
 the alignment step then incorporates this information to achieve higher accuracy . 
 the website is available at http://bioinfo.lifl.fr/magnolia . 
INTRODUCTION
METHODS
WEB SERVER
Input
Output
EXPERIMENTAL RESULTS
Results on pandit database
Results on BRaliBase II benchmark data