BACKGROUND
the non-coding rnas  play various vital roles in the biological systems  <cit> , such as gene-expression regulation  <cit> , catalysis  <cit> , signal recognition  <cit> , and ribosomal rna modification  <cit> .
given the facts that most of the human genome  is transcribed  <cit>  while only a small fraction of it  actually codes for proteins, it is tempting to hypothesize that the ncrnas contribute enormously to the complex and elegant regulatory networks in human and other multicellular organisms.
therefore, fully understanding any biological system is impossible without the thorough research on the ncrnas in it.
however, annotating ncrnas is more difficult than proteins, because ncrnas with divergent sequences may fold into conserved secondary structures, and still perform similar biological functions.
in this sense, secondary structure conservation is used as a better evidence for functional conservation than sequence similarity when conducting comparative ncrna analysis.
annotating the ncrna secondary structure is a prerequisite for comparative ncrna structural analysis.
however, determining ncrna secondary structure is a non-trivial task.
the performance of the existing computational methods  for predicting secondary structure from a single ncrna sequence is not satisfying, especially for long ncrna sequences  <cit> .
although the prediction accuracy can be improved with evolutionary information from multiple sequence alignments  <cit> , such information is not always available for every genome of interest.
on the other hand, genome-wide annotation of known ncrna families by homology search still appears as an open problem for lacking efficient and accurate computational pipelines.
for example, the latest release of the widely used software cmsearch has significantly improved the computational efficiency of its previous versions  <cit> .
however, it still would take about  <dig> hours to annotate the  <dig> gbp chicken genome with known rfam  <cit>  families on a 100-cpu cluster even with filters and mpi applied  <cit> .
the sensitivity of cmsearch reaches a plateau at ~87% without filters, indicating intrinsic difficulty in detecting ncrnas with diverse sequences.
the difficulty of ncrna annotation is partly due to the computational overhead of structure alignment, and partly due to the low information content given by the secondary structures  <cit> .
recent advances in massive parallel sequencing make genome-wide probing of ncrna secondary structures possible.
examples of technologies in this category include, but not limited to, pars  <cit> , fragseq  <cit> , and shape-seq  <cit>  .
with further improvements, such techniques are becoming more powerful for understanding the in vitro  <cit> , or even in vivo ncrna structrome  <cit> .
the information received from a typical genome-wide ncrna secondary structure probing experiment is the reactivity for each site.
as the probing reagents, such as 1m <dig>  <cit> , dms  <cit> , or nuclease  <cit> , are chosen to preferentially attack the paired/unpaired regions, the experimentally determined reactivity can be used to assess the probability of whether a specific site is paired.
the reactivities can then be transformed into pseudo-energy terms  <cit> , and be incorporated into existing rna-folding algorithms to predict the optimal secondary structure that is compatible with both the rna free energy models and the observed reactivity pattern.
when the reactivity information derived from shape technology  <cit>  was incorporated, the 16s rrna structure prediction accuracy was lifted from 47% to 97%  <cit> .
this success implies great potential in using the structure probing information in other comparative genome-wide ncrna analysis approaches.
therefore, it is possible to improve the ncrna annotation by incorporating the high-throughput rna secondary structure probing information.
first, the computational efficiency can be promoted by only focusing on transcribed regions revealed by the read-mapping pattern as used in standard rna-seq experiments.
in addition, the experimentally defined structural information can be used to reduce the search space of the alignment algorithms and lead to the development of a more efficient one.
meanwhile, we can also expect to improve the annotation accuracy because the experimentally determined structural information reflects the real rna structures, and is much more accurate than the in silico predictions.
here, we present a novel ncrna annotation algorithm called probealign, which, to the best of our knowledge, is the first algorithm that considers high-throughput rna structure probing information for the purpose of genome-wide ncrna annotation.
to make probealign feasible for large-scale sequencing data, the specific pairing relationships between bases in the query structures are discarded to achieve o time complexity.
on the other hand, with the usage of structure probing data, the partial structural aspects of target sequences are introduced into the algorithm.
therefore, probealign tackles the homology search problem from another perspective with the support of new technologies.
the benchmark results show that the prediction of probealign outperforms filter-based cmsearch with a shorter running time.
last but not least, the application of probealign to fragseq data, which was generated by high-throughput sequencing-based rna structure probing technology, shows its capability of analyzing genome-wide datasets.
the rest of the paper is organized as follows: in the methods section, we discuss the core algorithm of probealign and how to estimate the p-values for the alignment scores.
in the results section, we describe benchmark results, parameters optimization and an application of our algorithm to fragseq data.
in the discussion section, we summarize our existing works, and propose possible directions for future research.
methods
algorithm
probealign identifies the homologous ncrnas in a profile-based search manner.
the profile is generated by using the multiple sequence alignment of a given ncrna family.
the aligned columns formed by a majority of gap are excluded in the search profile.
in addition, the consensus structure of the family is considered as the structural information of the profile.
the targets of search are usually the genomic or transcriptomic sequences with experimentally determined reactivities.
in the latest implementation of probealign, higher reactivity of a site indicates higher chance of being unpaired, and vice versa.
assume the alphabet of rna sequences is {a, c, g, u, x}, in which x represents all unknown nucleotides.
first we denote the query of an ncrna family as q = {p, s}, where p is the sequence profile of the family and s is the pairing pattern in the corresponding consensus structure.
let the length of the profile be n, then p = 〈p <dig>  p <dig>  .
.
.
, pn〉 and s = 〈s <dig>  s <dig>  .
.
.
, sn〉.
here, pi=, which is a vector that contains the frequency of the nucleotides and gap at site i. si is a boolean value indicating whether site i is paired in the consensus structure or not .
note that the specific pairing relationship between sites in p is not considered in s, which is similar to the folded-blast  <cit> .
for target t of length m, denote b = 〈b <dig>  b <dig>  .
.
.
, bm〉 as the genomic sequence and r = 〈r <dig>  r <dig>  .
.
.
, rm〉 as the observed reactivities.
denote di,j, ii,j, mi,j as the optimal alignment scores for deleting, inserting and matching a column in the search profile, respectively.
they can be computed using the following recursive functions:
di,j=max{mi- <dig> j+ε0+εe,di- <dig> j+εe},ii,j=max{mi,j-1+ε0+εe,ii,j-1+εe},mi,j=max{di,j,ii,j,mi- <dig> j-1+α×τ+β×σ}.
here, ε <dig> and εe are the gap open penalty and the gap extension penalty, respectively.
in our implementation, a "semi-global alignment" setting  <cit>  is adopted.
therefore, these three functions are initialized with: m <dig>  =  <dig>  mi, <dig> = ε <dig> + i × εe, m <dig> j =  <dig>  and d <dig> j = ii,0= −∞.
τ and σ are functions to assess the structural and the sequence similarities between the queries and the targets, respectively.
α and β are weights assigned to these two types of similarities.
the sequence similarity between the query profile and the target sequence is computed using the following formula:
σ= ∑xϵ{a,c,g,u,x,-}vix×m.
where m is the substitution score between nucleotides x and y.
the general function to compute structural similarity is as follows:
τ=0if rjis not defined,fotherwise.
given the reactivity rj, p is computed to compare the structural aspect of bj with si.
πj is a random variable and πj ∈ { <dig>  1},  <dig> means bj is paired and  <dig> means bj is not paired.
according to the bayes' theorem, the probability can be computed as:
p=p×pΣπjp×p.
the probabilities p and p can be inferred from the reactivities retrieved from the rnas with known secondary structures  <cit> .
to simplify the computation, we assume p is equal to p and then define the function f as:
f=logp-logp=logp-logp.
note that the probability p varies among different probing techniques.
even for one protocol, the reactivity distributions may be different due to the distinct computational methods for transferring the chemical signals from biological experiments.
therefore, it may be hard to apply equation  <dig> on some techniques whose statistical properties have not been studied yet.
to overcome this limitation and make the implementation of probealign easy to use, a simplified scoring function is proposed:
f=1ifor,-1otherwise.
in equation  <dig>  rc is a cutoff value which is used to annotate the structural aspects of targets.
any site that has higher reactivity than rc is deemed as unpaired, and vice versa  = 1; rj <= rc ⇒ p = 1).
we have compared two different types of structural similarity functions by taking shape protocol as an example.
the benchmark results show that the optimal performance of those two functions is comparable.
therefore, the simplified scoring function is practical for universal usage, while the protocol-specific scoring function may be a better option if the reactivity distribution is known.
the above described dynamic programming algorithm computes the optimal alignment between the query profile and the target sequence with the consideration of both structural and sequence similarity.
after alignment, traceback is performed to check the base pairing consistency between the query structure and the target.
bonus scores are assigned to the possible pairing bases.
such additional information can be used to detect potential false positive hits that have high alignment scores but low structural consistency with the query.
for example, in figure  <dig>  two alignment scores are the same.
however, the target in alignment  <dig> is more conserved with the query, compared with the target in alignment  <dig>  because the red letters can form canonical pairs, while the green ones can not.
structure consistency scores can help us distinguish these two targets.
p-value estimation
a robust scheme for evaluating the statistical significance of prediction results is important for the homology search applications.
however, what statistical distribution the ncrna alignment scores should follow is still unclear.
in this case, we simulated the probealign scores by searching  <dig> rfam families  against five artificial sequences, whose gc content ranging from 30% to 70%.
each artificial sequence was constructed by concatenating random rna sequences generated by genrgens  <cit>  with a simple context-free grammar  <cit> .
the secondary structure of each random sequence was predicted by mfold  <cit> .
the corresponding reactivities of the secondary structure were simulated based on the shape technology  <cit> .
we fitted the probealign score density for each rfam family with four different distributions: the normal, gumbel, gev , and gamma distributions.
the goodness of fitting was measured with k-s test .
the fitting results on the five artificial sequences show that the probealign scores follow the gamma distribution for most of rfam families.
take the fitting on the artificial sequence with 50% gc content as an example.
out of  <dig> tested families,  <dig> families fit best with the gamma distribution, and the other three families  fit best with the normal distribution.
the score distribution fitting of the corona_fse family  and the rne <dig> family  is shown in figure  <dig>  it is clear that even rne <dig> fits better with the normal distribution, the gamma distribution also fit the probealign score distribution well.
so the gamma distribution was chosen to evaluate the p-values in probealign.
RESULTS
benchmarks
in this section, we will compare the performance of probealign and cmsearch using the rmark <dig> benchmark dataset.
this dataset contains  <dig> families, and each family has a training alignment and a test set.
the training alignments were employed to generate queries for both tools.
the sequences in the test sets were concatenated together and served as the target in the experiments.
the corresponding reactivities of the target were simulated based on the shape technology  <cit> .
to make the comparison between probealign and cmsearch fair, for each family, we kept the number of predictions of these two programs the same.
a server machine with  <dig> xeon i <dig> cpus  and  <dig> gb ram was used for the benchmarking and subsequent experiments under single core configuration.
cmsearch adopts the covariance model to query against the target sequences to detect rna homologs.
the recent release of cmsearch is coupled with hidden markov model -based filters to improve its computational efficiency  <cit> .
in the following experiments, cmsearch will be invoked with default setting, which means the filters are coupled and the default parameters are used.
for probealign, the weights for the structural and sequence similarity, α and β, were set to  <dig>  and  <dig> , respectively.
the simplified scoring function for structural similarity was used as default in the benchmarks.
according to the property of the shape reactivity data  <cit> , rc was set to  <dig> .
a detailed discussion of parameter selection will be presented in the following section.
the synthesized target contains  <dig> ncrna sequences  from the rmark <dig> dataset.
it takes  <dig>  minutes cpu time for probealign to finish the search while it takes  <dig>  minutes cpu time for cmsearch.
such improvement is expected, since probealign adopts an o algorithm, while the core algorithm of cmsearch is from o to o  <cit> , for a query with n sites and a target with m bases.
in terms of prediction accuracy, the overall tp/fp ratio of cmsearch is 632/ <dig>  while that of probealign is 653/ <dig>  of the  <dig> ncrna families in rmark <dig>  probealign generates different prediction results with cmsearch in  <dig> families.
table  <dig> shows the performance difference of probealign and cmsearch on those families.
only the families with different results between the two programs are shown in the table.
the search results for the trna and rnase_mrp families, whose roc curves are shown in figure  <dig>  clearly demonstrate the advantage of using the probing information to detect remote homologous sequences.
the sequence identities for these two families are 46% and 47%, which make it challenging for hmm-based filters to find the tested rnas.
note that it would be possible for cmsearch to predict more low sequence identity hits by disabling the filters, but it would dramatically  increase the running time  <cit> .
on the other hand, when the probing information is considered, the high structural similarity is able to compensate the low sequence similarity, and lift the ranking of ncrna sequences that are difficult to be detected by cmsearch.
figure  <dig> shows that a trna homolog  missed by cmsearch was identified by probealign.
of  <dig> sites in the profile of the training set,  <dig> sites have frequencies less than  <dig> % and  <dig> sites have frequencies between  <dig> % and 25%, which prevents the hmm filters to retrieve some trnas.
optimizing the structure and sequence similarity weights
in the probealign algorithm, the parameters α and β indicate the weights for the structural and sequence similarity, and control how the two types of information are incorporated into the dynamic programming algorithm.
the setting of these parameters should reflect how well the probing data would represent the actual secondary structure, as well as which information is more important in defining a specific ncrna family.
ideally, the setting of the parameters should be family-specific to satisfy the structure and the sequence conservation patterns.
however, it is tedious to define a set of parameters for each search profile, and more importantly, the overly tweaked parameters for the under-represented families would even bias the search.
in this case, it is expected to apply a set of universal parameters for all families.
three experiments have been conducted to analyze the effect of α and β on the performance of probealign by using the rmark <dig> dataset.
the value of α varied from  <dig> to  <dig> with an increasing step of  <dig> , while the value of β varied from  <dig> to  <dig> with a decreasing step of - <dig> .
in the first experiment, we investigated the performance of probealign with the default setting under different combinations of α and β. in the second experiment, we excluded the structure consistency score to investigate its contribution to the overall performance.
in the third experiment, the prediction was based upon the shape-specific scoring function for structural similarity.
figure  <dig> shows the performance of probealign in these three experiments.
for the first experiment , the optimal performance is achieved at α =  <dig>  and β =  <dig> , which is then taken as the default setting for the algorithm.
for the second experiment , the optimal performance is achieved at α =  <dig>  and β =  <dig> .
the performance of probealign is higher than that without considering the structure consistency score.
such improvement is more significant when the structural weight is higher.
therefore structure consistency score is an effective way of improving the overall performance.
in the last experiment, we adopted the shape-specific scoring function to evaluate the structural similarity between the rfam families and the target sequence.
we can see that the optimal performance for the shape-specific function  and the default simplified function  is comparable: 656/ <dig> at α =  <dig>  and β =  <dig>  for the shape-specific scoring function; 653/ <dig> at α =  <dig>  and β =  <dig>  for original simplified scoring function.
the performance difference is increased when raising the ratio of α/β.
therefore, the protocol-specific scoring function may be a better choice if the underlying reactivity distribution is known.
the implementation of probealign allows users to decide which scoring function they use.
high-throughput sequencing-based rna structure probing data
fragseq  is a genome-wide rna structure probing technique that has been applied to study the mouse nuclear transcriptome  <cit> .
the rna secondary structures in the kh <dig> undifferentiated mouse embryonic stem cells  and neural precursors cells  were probed.
by analyzing nine snrna families  in the mouse genome, the paper shows a good accordance between the probing data and the real secondary structures.
new secondary structures have also been proposed to three other snrna families , showing the ability of fragseq to discover novel ncrna transcripts and their secondary structures.
we used probealign with default setting to search the nine snrnas families against the fragseq data to demonstrate its utility on experimentally determined reactivities.
we were only interested in the genomic regions that were transcribed, i.e.
being covered by more than  <dig> sequenced reads.
there are  <dig>  regions  for the undiff cell line and  <dig>  regions  for the d5np cell line.
the reactivities for these regions were computed using fragseq v <dig> .
<dig>  a supplementary software for the probing protocol  <cit> .
because fragseq is a different technology than shape, rc was adjusted to  <dig>  from  <dig> .
all other parameters remained the same as in the benchmark.
a universal p-value cutoff  was set for all searches.
the running time for the undiff dataset was  <dig>  minutes cpu time, and for the d5np dataset was  <dig>  minutes cpu time.
during the analysis of the predicted results, we found some reads were mapped onto repeat regions in the genome.
those hits were removed by using repbase database  <cit> .
the final search results are summarized in table  <dig>  u <dig> and u <dig> have no record in repbase.
only  <dig> and  <dig> u <dig> records in repbase are covered by the transcribed regions of d5np and undiff cell lines, and all of them are top ranked in the results of probealign.
the corresponding sequences with their locations on the genome can be downloaded at http://genome.ucf.edu/probealign.
the numbers in the brackets show that how many predictions by probealign are recorded in repbase.
one interesting observation from the probealign search results is that the transcription of u <dig> and u <dig> snrna families are more active in undiff cells than in d5np cells.
it is not surprising to see the potential correlation between the u <dig> and u <dig> transcription level, as they have been proposed to interact with each other in splicing control.
in fact, it is hypothesized that they can bind with each other due to a long complementary sequence between them  <cit> .
recent experiments show that the snrnas in un-proliferated stem cells have higher expression than in proliferated cells  <cit> .
the observation is explained by the snrnas playing an important role in ribosome biogenesis, cellular proliferation and pre-mrna splicing  <cit> .
from the probealign search results, we can further conclude that not only the expression level of the snrna is higher in un-proliferated cells, there are actually more u <dig> and u <dig> snrna genes being transcribed in un-proliferated stem cells.
discussion and
CONCLUSIONS
in this article, we have proposed a novel algorithm, probealign, for incorporating high-throughput sequencing-based rna structure probing data into ncrna homology search.
to our knowledge, this is the first application of structure probing information to rna functional annotation.
this integration makes the accuracy of probealign even higher than the cmsearch tool, especially for ncrna homologs with low sequence identity.
in addition, the time complexity of the algorithm is o, which is feasible for handling genome-wide datasets.
probealign itself can also act as a filter for more detailed downstream alignment algorithms.
considering both probealign and the hmm filters in cmsearch being o time complexity algorithms, they should have comparable time efficiency if similarly optimized.
it is clear that probealign guarantees higher sensitivity and specificity.
in this case, probealign can be coupled with more accurate alignment algorithms such as cmsearch itself, or other structure-sequence alignment algorithms such as fastr  <cit> , pfastr  <cit> , and rsearch  <cit> .
we are also developing a new structure-sequence alignment algorithm that takes into account the probing information, which can also be used as the downstream detailed alignment after probealign screening.
in conclusion, we present here an accurate and efficient rna homology search algorithm, probealign, which incorporates the high-throughput sequencing-based rna structure probing information.
with the increasing requirement of genome-wide ncrna annotation, we anticipate that more rna transcripts, and their secondary structures and functionalities, will be annotated by using probealign.
competing interests
the authors declare that they have no competing interests.
authors' contributions
sz contributed with the conception of the research.
pg, cz, and sz designed the algorithm.
pg implemented the algorithm and conducted the experiments.
pg, cz, and sz wrote the manuscript.
all authors read and approved the final manuscript.

 the non-coding rnas play various vital roles in the biological systems, such as gene-expression regulation, catalysis, signal recognition, and ribosomal rna modification. given the facts that most of the human genome is transcribed while only a small fraction of it actually codes for proteins, it is tempting to hypothesize that the ncrnas contribute enormously to the complex and elegant regulatory networks in human and other multicellular organisms. therefore, fully understanding any biological system is impossible without the thorough research on the ncrnas in it. however, annotating ncrnas is more difficult than proteins, because ncrnas with divergent sequences may fold into conserved secondary structures, and still perform similar biological functions. in this sense, secondary structure conservation is used as a better evidence for functional conservation than sequence similarity when conducting comparative ncrna analysis. annotating the ncrna secondary structure is a prerequisite for comparative ncrna structural analysis. however, determining ncrna secondary structure is a non-trivial task. the performance of the existing computational methods for predicting secondary structure from a single ncrna sequence is not satisfying, especially for long ncrna sequences. although the prediction accuracy can be improved with evolutionary information from multiple sequence alignments, such information is not always available for every genome of interest. on the other hand, genome-wide annotation of known ncrna families by homology search still appears as an open problem for lacking efficient and accurate computational pipelines. for example, the latest release of the widely used software cmsearch has significantly improved the computational efficiency of its previous versions. however, it still would take about hours to annotate the gbp chicken genome with known rfam families on a 100-cpu cluster even with filters and mpi applied. the sensitivity of cmsearch reaches a plateau at ~87% without filters, indicating intrinsic difficulty in detecting ncrnas with diverse sequences. the difficulty of ncrna annotation is partly due to the computational overhead of structure alignment, and partly due to the low information content given by the secondary structures. recent advances in massive parallel sequencing make genome-wide probing of ncrna secondary structures possible. examples of technologies in this category include, but not limited to, pars, fragseq, and shape-seq. with further improvements, such techniques are becoming more powerful for understanding the in vitro, or even in vivo ncrna structrome. the information received from a typical genome-wide ncrna secondary structure probing experiment is the reactivity for each site. as the probing reagents, such as 1m, dms, or nuclease, are chosen to preferentially attack the paired/unpaired regions, the experimentally determined reactivity can be used to assess the probability of whether a specific site is paired. the reactivities can then be transformed into pseudo-energy terms, and be incorporated into existing rna-folding algorithms to predict the optimal secondary structure that is compatible with both the rna free energy models and the observed reactivity pattern. when the reactivity information derived from shape technology was incorporated, the 16s rrna structure prediction accuracy was lifted from 47% to 97%. this success implies great potential in using the structure probing information in other comparative genome-wide ncrna analysis approaches. therefore, it is possible to improve the ncrna annotation by incorporating the high-throughput rna secondary structure probing information. first, the computational efficiency can be promoted by only focusing on transcribed regions revealed by the read-mapping pattern as used in standard rna-seq experiments. in addition, the experimentally defined structural information can be used to reduce the search space of the alignment algorithms and lead to the development of a more efficient one. meanwhile, we can also expect to improve the annotation accuracy because the experimentally determined structural information reflects the real rna structures, and is much more accurate than the in silico predictions. here, we present a novel ncrna annotation algorithm called probealign, which, to the best of our knowledge, is the first algorithm that considers high-throughput rna structure probing information for the purpose of genome-wide ncrna annotation. to make probealign feasible for large-scale sequencing data, the specific pairing relationships between bases in the query structures are discarded to achieve o time complexity. on the other hand, with the usage of structure probing data, the partial structural aspects of target sequences are introduced into the algorithm. therefore, probealign tackles the homology search problem from another perspective with the support of new technologies. the benchmark results show that the prediction of probealign outperforms filter-based cmsearch with a shorter running time. last but not least, the application of probealign to fragseq data, which was generated by high-throughput sequencing-based rna structure probing technology, shows its capability of analyzing genome-wide datasets. the rest of the paper is organized as follows: in the methods section, we discuss the core algorithm of probealign and how to estimate the p-values for the alignment scores. in the results section, we describe benchmark results, parameters optimization and an application of our algorithm to fragseq data. in the discussion section, we summarize our existing works, and propose possible directions for future research. methods algorithm probealign identifies the homologous ncrnas in a profile-based search manner. the profile is generated by using the multiple sequence alignment of a given ncrna family. the aligned columns formed by a majority of gap are excluded in the search profile. in addition, the consensus structure of the family is considered as the structural information of the profile. the targets of search are usually the genomic or transcriptomic sequences with experimentally determined reactivities. in the latest implementation of probealign, higher reactivity of a site indicates higher chance of being unpaired, and vice versa. assume the alphabet of rna sequences is {a, c, g, u, x}, in which x represents all unknown nucleotides. first we denote the query of an ncrna family as q = {p, s}, where p is the sequence profile of the family and s is the pairing pattern in the corresponding consensus structure. let the length of the profile be n, then p = 〈p p..., pn〉 and s = 〈s s..., sn〉. here, pi=, which is a vector that contains the frequency of the nucleotides and gap at site i. si is a boolean value indicating whether site i is paired in the consensus structure or not. note that the specific pairing relationship between sites in p is not considered in s, which is similar to the folded-blast. for target t of length m, denote b = 〈b b..., bm〉 as the genomic sequence and r = 〈r r..., rm〉 as the observed reactivities. denote di,j, ii,j, mi,j as the optimal alignment scores for deleting, inserting and matching a column in the search profile, respectively. they can be computed using the following recursive functions: di,j=max{mi- j+ε0+εe,di- j+εe},ii,j=max{mi,j-1+ε0+εe,ii,j-1+εe},mi,j=max{di,j,ii,j,mi- j-1+α×τ+β×σ}. here, ε and εe are the gap open penalty and the gap extension penalty, respectively. in our implementation, a "semi-global alignment" setting is adopted. therefore, these three functions are initialized with: m = mi, = ε + i × εe, m j = and d j = ii,0= −∞. τ and σ are functions to assess the structural and the sequence similarities between the queries and the targets, respectively. α and β are weights assigned to these two types of similarities. the sequence similarity between the query profile and the target sequence is computed using the following formula: σ= ∑xϵ{a,c,g,u,x,-}vix×m. where m is the substitution score between nucleotides x and y. the general function to compute structural similarity is as follows: τ=0if rjis not defined,fotherwise. given the reactivity rj, p is computed to compare the structural aspect of bj with si. πj is a random variable and πj ∈ { 1}, means bj is paired and means bj is not paired. according to the bayes' theorem, the probability can be computed as: p=p×pΣπjp×p. the probabilities p and p can be inferred from the reactivities retrieved from the rnas with known secondary structures. to simplify the computation, we assume p is equal to p and then define the function f as: f=logp-logp=logp-logp. note that the probability p varies among different probing techniques. even for one protocol, the reactivity distributions may be different due to the distinct computational methods for transferring the chemical signals from biological experiments. therefore, it may be hard to apply equation on some techniques whose statistical properties have not been studied yet. to overcome this limitation and make the implementation of probealign easy to use, a simplified scoring function is proposed: f=1ifor,-1otherwise. in equation rc is a cutoff value which is used to annotate the structural aspects of targets. any site that has higher reactivity than rc is deemed as unpaired, and vice versa = 1; rj <= rc ⇒ p = 1). we have compared two different types of structural similarity functions by taking shape protocol as an example. the benchmark results show that the optimal performance of those two functions is comparable. therefore, the simplified scoring function is practical for universal usage, while the protocol-specific scoring function may be a better option if the reactivity distribution is known. the above described dynamic programming algorithm computes the optimal alignment between the query profile and the target sequence with the consideration of both structural and sequence similarity. after alignment, traceback is performed to check the base pairing consistency between the query structure and the target. bonus scores are assigned to the possible pairing bases. such additional information can be used to detect potential false positive hits that have high alignment scores but low structural consistency with the query. for example, in figure two alignment scores are the same. however, the target in alignment is more conserved with the query, compared with the target in alignment because the red letters can form canonical pairs, while the green ones can not. structure consistency scores can help us distinguish these two targets. p-value estimation a robust scheme for evaluating the statistical significance of prediction results is important for the homology search applications. however, what statistical distribution the ncrna alignment scores should follow is still unclear. in this case, we simulated the probealign scores by searching rfam families against five artificial sequences, whose gc content ranging from 30% to 70%. each artificial sequence was constructed by concatenating random rna sequences generated by genrgens with a simple context-free grammar. the secondary structure of each random sequence was predicted by mfold. the corresponding reactivities of the secondary structure were simulated based on the shape technology. we fitted the probealign score density for each rfam family with four different distributions: the normal, gumbel, gev, and gamma distributions. the goodness of fitting was measured with k-s test. the fitting results on the five artificial sequences show that the probealign scores follow the gamma distribution for most of rfam families. take the fitting on the artificial sequence with 50% gc content as an example. out of tested families, families fit best with the gamma distribution, and the other three families fit best with the normal distribution. the score distribution fitting of the corona_fse family and the rne family is shown in figure it is clear that even rne fits better with the normal distribution, the gamma distribution also fit the probealign score distribution well. so the gamma distribution was chosen to evaluate the p-values in probealign.  benchmarks in this section, we will compare the performance of probealign and cmsearch using the rmark benchmark dataset. this dataset contains families, and each family has a training alignment and a test set. the training alignments were employed to generate queries for both tools. the sequences in the test sets were concatenated together and served as the target in the experiments. the corresponding reactivities of the target were simulated based on the shape technology. to make the comparison between probealign and cmsearch fair, for each family, we kept the number of predictions of these two programs the same. a server machine with xeon i cpus and gb ram was used for the benchmarking and subsequent experiments under single core configuration. cmsearch adopts the covariance model to query against the target sequences to detect rna homologs. the recent release of cmsearch is coupled with hidden markov model -based filters to improve its computational efficiency. in the following experiments, cmsearch will be invoked with default setting, which means the filters are coupled and the default parameters are used. for probealign, the weights for the structural and sequence similarity, α and β, were set to and, respectively. the simplified scoring function for structural similarity was used as default in the benchmarks. according to the property of the shape reactivity data, rc was set to. a detailed discussion of parameter selection will be presented in the following section. the synthesized target contains ncrna sequences from the rmark dataset. it takes minutes cpu time for probealign to finish the search while it takes minutes cpu time for cmsearch. such improvement is expected, since probealign adopts an o algorithm, while the core algorithm of cmsearch is from o to o, for a query with n sites and a target with m bases. in terms of prediction accuracy, the overall tp/fp ratio of cmsearch is 632/ while that of probealign is 653/ of the ncrna families in rmark probealign generates different prediction results with cmsearch in families. table shows the performance difference of probealign and cmsearch on those families. only the families with different results between the two programs are shown in the table. the search results for the trna and rnase_mrp families, whose roc curves are shown in figure clearly demonstrate the advantage of using the probing information to detect remote homologous sequences. the sequence identities for these two families are 46% and 47%, which make it challenging for hmm-based filters to find the tested rnas. note that it would be possible for cmsearch to predict more low sequence identity hits by disabling the filters, but it would dramatically increase the running time. on the other hand, when the probing information is considered, the high structural similarity is able to compensate the low sequence similarity, and lift the ranking of ncrna sequences that are difficult to be detected by cmsearch. figure shows that a trna homolog missed by cmsearch was identified by probealign. of sites in the profile of the training set, sites have frequencies less than % and sites have frequencies between % and 25%, which prevents the hmm filters to retrieve some trnas. optimizing the structure and sequence similarity weights in the probealign algorithm, the parameters α and β indicate the weights for the structural and sequence similarity, and control how the two types of information are incorporated into the dynamic programming algorithm. the setting of these parameters should reflect how well the probing data would represent the actual secondary structure, as well as which information is more important in defining a specific ncrna family. ideally, the setting of the parameters should be family-specific to satisfy the structure and the sequence conservation patterns. however, it is tedious to define a set of parameters for each search profile, and more importantly, the overly tweaked parameters for the under-represented families would even bias the search. in this case, it is expected to apply a set of universal parameters for all families. three experiments have been conducted to analyze the effect of α and β on the performance of probealign by using the rmark dataset. the value of α varied from to with an increasing step of, while the value of β varied from to with a decreasing step of -. in the first experiment, we investigated the performance of probealign with the default setting under different combinations of α and β. in the second experiment, we excluded the structure consistency score to investigate its contribution to the overall performance. in the third experiment, the prediction was based upon the shape-specific scoring function for structural similarity. figure shows the performance of probealign in these three experiments. for the first experiment, the optimal performance is achieved at α = and β =, which is then taken as the default setting for the algorithm. for the second experiment, the optimal performance is achieved at α = and β =. the performance of probealign is higher than that without considering the structure consistency score. such improvement is more significant when the structural weight is higher. therefore structure consistency score is an effective way of improving the overall performance. in the last experiment, we adopted the shape-specific scoring function to evaluate the structural similarity between the rfam families and the target sequence. we can see that the optimal performance for the shape-specific function and the default simplified function is comparable: 656/ at α = and β = for the shape-specific scoring function; 653/ at α = and β = for original simplified scoring function. the performance difference is increased when raising the ratio of α/β. therefore, the protocol-specific scoring function may be a better choice if the underlying reactivity distribution is known. the implementation of probealign allows users to decide which scoring function they use. high-throughput sequencing-based rna structure probing data fragseq is a genome-wide rna structure probing technique that has been applied to study the mouse nuclear transcriptome. the rna secondary structures in the kh undifferentiated mouse embryonic stem cells and neural precursors cells were probed. by analyzing nine snrna families in the mouse genome, the paper shows a good accordance between the probing data and the real secondary structures. new secondary structures have also been proposed to three other snrna families, showing the ability of fragseq to discover novel ncrna transcripts and their secondary structures. we used probealign with default setting to search the nine snrnas families against the fragseq data to demonstrate its utility on experimentally determined reactivities. we were only interested in the genomic regions that were transcribed, i.e. being covered by more than sequenced reads. there are regions for the undiff cell line and regions for the d5np cell line. the reactivities for these regions were computed using fragseq v. a supplementary software for the probing protocol. because fragseq is a different technology than shape, rc was adjusted to from. all other parameters remained the same as in the benchmark. a universal p-value cutoff was set for all searches. the running time for the undiff dataset was minutes cpu time, and for the d5np dataset was minutes cpu time. during the analysis of the predicted results, we found some reads were mapped onto repeat regions in the genome. those hits were removed by using repbase database. the final search results are summarized in table u and u have no record in repbase. only and u records in repbase are covered by the transcribed regions of d5np and undiff cell lines, and all of them are top ranked in the results of probealign. the corresponding sequences with their locations on the genome can be downloaded at http://genome.ucf.edu/probealign. the numbers in the brackets show that how many predictions by probealign are recorded in repbase. one interesting observation from the probealign search results is that the transcription of u and u snrna families are more active in undiff cells than in d5np cells. it is not surprising to see the potential correlation between the u and u transcription level, as they have been proposed to interact with each other in splicing control. in fact, it is hypothesized that they can bind with each other due to a long complementary sequence between them. recent experiments show that the snrnas in un-proliferated stem cells have higher expression than in proliferated cells. the observation is explained by the snrnas playing an important role in ribosome biogenesis, cellular proliferation and pre-mrna splicing. from the probealign search results, we can further conclude that not only the expression level of the snrna is higher in un-proliferated cells, there are actually more u and u snrna genes being transcribed in un-proliferated stem cells. discussion and  in this article, we have proposed a novel algorithm, probealign, for incorporating high-throughput sequencing-based rna structure probing data into ncrna homology search. to our knowledge, this is the first application of structure probing information to rna functional annotation. this integration makes the accuracy of probealign even higher than the cmsearch tool, especially for ncrna homologs with low sequence identity. in addition, the time complexity of the algorithm is o, which is feasible for handling genome-wide datasets. probealign itself can also act as a filter for more detailed downstream alignment algorithms. considering both probealign and the hmm filters in cmsearch being o time complexity algorithms, they should have comparable time efficiency if similarly optimized. it is clear that probealign guarantees higher sensitivity and specificity. in this case, probealign can be coupled with more accurate alignment algorithms such as cmsearch itself, or other structure-sequence alignment algorithms such as fastr, pfastr, and rsearch. we are also developing a new structure-sequence alignment algorithm that takes into account the probing information, which can also be used as the downstream detailed alignment after probealign screening. in conclusion, we present here an accurate and efficient rna homology search algorithm, probealign, which incorporates the high-throughput sequencing-based rna structure probing information. with the increasing requirement of genome-wide ncrna annotation, we anticipate that more rna transcripts, and their secondary structures and functionalities, will be annotated by using probealign. competing interests the authors declare that they have no competing interests. authors' contributions sz contributed with the conception of the research. pg, cz, and sz designed the algorithm. pg implemented the algorithm and conducted the experiments. pg, cz, and sz wrote the manuscript. all authors read and approved the final manuscript. 
the benchmark results show that the prediction accuracy of probealign outperforms filter-based cmsearch with high computational efficiency. in this paper, we present a novel approach, probealign, to incorporate the reactivities from high-throughput rna structure probing into ncrna homology search for functional annotation. it is a promising tool for ncrna functional annotation on genome-wide datasets. on the other hand, the partial structural information of the target sequences embedded in probing data is retrieved to guide the alignment. recent advances in rna structure probing technologies, including the ones based on high-throughput sequencing, have improved the accuracy of thermodynamic folding with quantitative nucleotide-resolution structural information. rna structure probinghigh-throughput sequencingrna secondary structurehomology search march- april recomb-seq: fourth annual recomb satellite workshop on massively parallel sequencing pittsburgh, pa, usa by incorporating high-throughput sequencing-based structure probing information, probealign can improve the accuracy and efficiency of ncrna homology search. the application of probealign to the fragseq data, which is based on genome-wide structure probing, has demonstrated its capability to search ncrnas in a large-scale dataset from high-throughput sequencing. to reduce the overhead of structure alignment on large-scale data, the specific pairing patterns in the query sequences are ignored. thus the structure alignment problem is transformed into a sequence alignment problem with additional reactivity information.
 recent advances in rna structure probing technologies, including the ones based on high-throughput sequencing, have improved the accuracy of thermodynamic folding with quantitative nucleotide-resolution structural information.  in this paper, we present a novel approach, probealign, to incorporate the reactivities from high-throughput rna structure probing into ncrna homology search for functional annotation. to reduce the overhead of structure alignment on large-scale data, the specific pairing patterns in the query sequences are ignored. on the other hand, the partial structural information of the target sequences embedded in probing data is retrieved to guide the alignment. thus the structure alignment problem is transformed into a sequence alignment problem with additional reactivity information. the benchmark results show that the prediction accuracy of probealign outperforms filter-based cmsearch with high computational efficiency. the application of probealign to the fragseq data, which is based on genome-wide structure probing, has demonstrated its capability to search ncrnas in a large-scale dataset from high-throughput sequencing.  by incorporating high-throughput sequencing-based structure probing information, probealign can improve the accuracy and efficiency of ncrna homology search. it is a promising tool for ncrna functional annotation on genome-wide datasets. availability the source code of probealign is available at http://genome.ucf.edu/probealign. rna structure probinghigh-throughput sequencingrna secondary structurehomology search march- april recomb-seq: fourth annual recomb satellite workshop on massively parallel sequencing pittsburgh, pa, usa 