alignment - based methods are widely used for identifying non - coding rnas in genomes ( 1,2 ) . blast ( 3 )
is a popular tool for this task but recently a partition function - based approach ( 4,5 ) and semi - global alignment approaches have also been applied ( 6,7 ) .
the partition function - based approach , which was proposed by us previously , is a local alignment tuning of the probalign program ( 10,11 ) to detect potential homologous non - coding rna ( ncrna ) sequences in large genomes .
( 5 ) show that the partition function - based approach achieves a significantly higher accuracy than the popular blast program and the smith  waterman local alignment implementation in ssearch ( 8) on benchmarks constructed from the rfam ncrna sequence database ( 9 ) . here , we present an online implementation of a simple algorithm that identifies all putative homologs in a given genome using the modified probalign program .
this probability was earlier shown to be a better discriminator of true hits from false ones than the blast and ssearch z - scores ( 5 ) .
the latter is designed for multiple alignment of protein and rna / dna sequences and can not handle large sequences .
our new server is designed specifically for blast like homology search and identifies all potential homologs in a target genome ( see homology search algorithm below ) .
the server takes as input single or multiple query rna sequences and a target genome sequence both in fasta format .
it returns an error if the data contains characters other than iupac abbreviations or is not in fasta format .
the user can specify the gap penalties and the thermodynamic temperature t ( figure 1 ) .
these were optimized on the training set of the rna - genome benchmark ( 5 ) that can be found at http://www.cs.njit.edu/usman/rnagenome .
this benchmark contains ncrnas aligned to putative homologs ( as given by rfam seed alignments ) with large dna flanks . 

we also provide a subset of sequences in the 26 divergent rfam families ( average pairwise identity at most 60% ) that were used in our earlier study ( 5 ) .
the user can scan the genome for sequences in the family by simply selecting their family of interest using the drop - down box ( figure 1 ) .
the probalign strategy is to use suboptimal alignments determined by the input parameters to compute posterior probabilities from which the final alignment is produced ( 5,11 )
. a large value of t would include suboptimal alignments with much lower scores than the optimal , whereas a value of 0 would use just the optimal alignments .
the mean posterior probability of an alignment is calculated by averaging across the posterior probability of each aligned nucleotide ( these are automatically produced by probalign ) .
the server outputs all alignments between query and its similar sequence in the genome that have mean posterior probability at least the user specified threshold . by default
the server accepts an email address to inform the user that the results are ready .
the main server page also lists links to standalone software and rna to genome alignment benchmarks that were used in ref .
while the job is being run we show the user the percentage completed ( figure 2 ) .
the output alignment can be viewed in simple text or using the plast - ncrna alignment viewer in a format tuned for local alignment .
the alignment start and end are the first and last match / mismatch aligned nucleotide and every 10 aligned nucleotides are annotated with their positions in the query and target ( figure 3 ) . 

this can be saved to the local disk or copied and pasted into files . in the text output option
( figure 3 ) , the posterior probability for each aligned nucleotide is multiplied by 10 and then rounded to the next highest integer .
thus , a value of 4 means the posterior probability is between 0.3 and 0.4 ( but excluding 0.3 ) .
the viewer is a java applet that allows the user to see a list of all hits found ( sorted by the mean posterior probability ) and the aligned nucleotides colored by the posterior probability ( figure 4 ) . by clicking on a hit
when the mouse is rolled over an aligned nucleotide the actual posterior probability is displayed . 

figure 4.the plast - ncrna alignment viewer applet provides a list of all hits sorted by their mean posterior probability and colored aligned nucleotides with intensity proportional to the posterior probability .
the plast - ncrna alignment viewer applet provides a list of all hits sorted by their mean posterior probability and colored aligned nucleotides with intensity proportional to the posterior probability .
our server implements a simple algorithm that replaces the portion of the target aligned to the query with a string of n 's of equal length and realigns the query .
this process repeats until no alignment of posterior probability above the user - specified threshold is found or an alignment of zero posterior probability is encountered ( to ensure termination ) . instead of replacing previously aligned portions with the string of
however , this destroys the structure of the target genome and may lead to false hits .
the exact running time and spare requirements for aligning a query of length m to a target of length n is o(mn ) . for target sequences of length
the output contains hits found in all the slices and shows the nucleotide positions in the original target instead of the 15 k slice .
this does not limit the usage of the server since ncrnas are usually much shorter than this length as determined by rfam sequences .
we provide two test examples for users interested in seeing a test run of our server . in the first case ,
the query is a ribonuclease p rna sequence ( rnasep bact a rfam family ) and the target is a clavibacter michiganensis complete genome ( 3 297 891 bp ) . in the second one
the query is a pea u4 snrna sequence ( u4 rfam family ) and the target is a phytophthora infestans whole genome sequence ( 582 831 bp ) .
both the targets contain at least one putatively homologous rna to their queries as given by rfam family alignments .
the nucleotide positions of the homologs are listed in the information links on the example page .
the server takes 30 and 3 min to return results for the first and second test cases , respectively . in the first case , hit
number 21 with mean posterior probability of 0.25 and in the second one hit 2 with mean posterior probability of 0.32 ( figure 4 ) identify the putative homolog as given by rfam ( hits are identified by nucleotide positions ) .
our server also identifies additional hits of comparable mean posterior probability to the putative homolog .
we tested multiple queries by selecting the u4 family and aligning it to the phytophthora infestans whole - genome sequence ( same one used above ) .
the server took 58 min to finish and in all 24 queries found the putative homolog given by rfam .
we provide a webserver that implements local alignment based on partition function posterior probablities and is specifically tuned for aligning query ncrna sequences to putative homologs in large genomes .
united states national science foundation ( grant 033 - 1654 to cipres cluster ) . funding for open access charge :
 alignment - based programs are valuable tools for finding potential homologs in genome sequences . 
 previously , it has been shown that partition function posterior probabilities attuned to local alignment achieve a high accuracy in identifying distantly similar non - coding rna sequences that are hidden in a large genome . here , we present an online implementation of that alignment algorithm based on such probabilities . 
 our server takes as input a query rna sequence and a large genome sequence , and outputs a list of hits that are above a mean posterior probability threshold . 
 the output is presented in a format suited to local alignment . 
 it can also be viewed within the plast alignment viewer applet that provides a list of all hits found and highlights regions of high posterior probability within each local alignment . 
 the server is freely available at http://plastrna.njit.edu . 
INTRODUCTION
INPUT PARAMETERS
OUTPUT AND ANALYSIS
HOMOLOGY SEARCH ALGORITHM
SERVER PERFORMANCE
CONCLUSION
FUNDING