Human MicroRNA Target Prediction via Multi-Hypotheses Learning.

MicroRNAs are involved in many critical cellular activities through binding to their mRNA targets, for example, in cell proliferation, differentiation, death, growth control, and developmental timing. Prediction of microRNA targets can assist in efficient experimental investigations on the functional roles of these small noncoding RNAs. Their accurate prediction, however, remains a challenge due to the limited understanding of underlying processes in recognizing microRNA targets. In this article, we introduce an algorithm that aims at not only predicting microRNA targets accurately but also assisting in vivo experiments to understand the mechanisms of targeting. The algorithm learns a unique hypothesis for each possible mechanism of microRNA targeting. These hypotheses are utilized to build a superior target predictor and for biologically meaningful partitioning of the data set of microRNA-target duplexes. Experimentally verified features for recognizing targets that incorporated in the algorithm enable the establishment of hypotheses that can be correlated with target recognition mechanisms. Our results and analysis show that our algorithm outperforms state-of-the-art data-driven approaches such as deep learning models and machine learning algorithms and rule-based methods for instance miRanda and RNAhybrid. In addition, feature selection on the partitions, provided by our algorithm, confirms that the partitioning mechanism is closely related to biological mechanisms of microRNA targeting. The resulting data partitions can potentially be used for in vivo experiments to aid in the discovery of the targeting mechanisms.

A carnivorous plant genetic map: pitcher/insect-capture QTL on a genetic linkage map of Sarracenia.

The study of carnivorous plants can afford insight into their unique evolutionary adaptations and their interactions with prokaryotic and eukaryotic species. For Sarracenia (pitcher plants), we identified 64 quantitative trait loci (QTL) for insect-capture traits of the pitchers, providing the genetic basis for differences between the pitfall and lobster-trap strategies of insect capture. The linkage map developed here is based upon the F2 of a cross between Sarracenia rosea and Sarracenia psittacina; we mapped 437 single nucleotide polymorphism and simple sequence repeat markers. We measured pitcher traits which differ between S. rosea and S. psittacina, mapping 64 QTL for 17 pitcher traits; there are hot-spot locations where multiple QTL map near each other. There are epistatic interactions in many cases where there are multiple loci for a trait. The QTL map uncovered the genetic basis for the differences between pitfall- and lobster-traps, and the changes that occurred during the divergence of these species. The longevity and clonability of Sarracenia plants make the F2 mapping population a resource for mapping more traits and for phenotype-to-genotype studies.

Accurate prediction of human miRNA targets via graph modeling of the miRNA-target duplex.

miRNAs are involved in many critical cellular activities through binding to their mRNA targets, e.g. in cell proliferation, differentiation, death, growth control, and developmental timing. Accurate prediction of miRNA targets can assist efficient experimental investigations on the functional roles of miRNAs. Their prediction, however, remains a challengeable task due to the lack of experimental data about the tertiary structure of miRNA-target binding duplexes. In particular, correlations of nucleotides in the binding duplexes may not be limited to the canonical Watson Crick base pairs (BPs) as they have been perceived; methods based on secondary structure prediction (typically minimum free energy (MFE)) have only had mix success. In this work, we characterized miRNA binding duplexes with a graph model to capture the correlations between pairs of nucleotides of an miRNA and its target sequences. We developed machine learning algorithms to train the graph model to predict the target sites of miRNAs. In particular, because imbalance between positive and negative samples can significantly deteriorate the performance of machine learning methods, we designed a novel method to re-sample available dataset to produce more informative data learning process. We evaluated our model and miRNA target prediction method on human miRNAs and target data obtained from mirTarBase, a database of experimentally verified miRNA-target interactions. The performance of our method in target prediction achieved a sensitivity of 86% with a false positive rate below 13%. In comparison with the state-of-the-art methods miRanda and RNAhybrid on the test data, our method outperforms both of them by a significant margin. The source codes, test sets and model files all are available at http://rna-informatics.uga.edu/?f=software&p=GraB-miTarget .

UGbS-Flex, a novel bioinformatics pipeline for imputation-free SNP discovery in polyploids without a reference genome: finger millet as a case study.

BACKGROUND: Research on orphan crops is often hindered by a lack of genomic resources. With the advent of affordable sequencing technologies, genotyping an entire genome or, for large-genome species, a representative fraction of the genome has become feasible for any crop. Nevertheless, most genotyping-by-sequencing (GBS) methods are geared towards obtaining large numbers of markers at low sequence depth, which excludes their application in heterozygous individuals. Furthermore, bioinformatics pipelines often lack the flexibility to deal with paired-end reads or to be applied in polyploid species. RESULTS: UGbS-Flex combines publicly available software with in-house python and perl scripts to efficiently call SNPs from genotyping-by-sequencing reads irrespective of the species' ploidy level, breeding system and availability of a reference genome. Noteworthy features of the UGbS-Flex pipeline are an ability to use paired-end reads as input, an effective approach to cluster reads across samples with enhanced outputs, and maximization of SNP calling. We demonstrate use of the pipeline for the identification of several thousand high-confidence SNPs with high representation across samples in an F3-derived F2 population in the allotetraploid finger millet. Robust high-density genetic maps were constructed using the time-tested mapping program MAPMAKER which we upgraded to run efficiently and in a semi-automated manner in a Windows Command Prompt Environment. We exploited comparative GBS with one of the diploid ancestors of finger millet to assign linkage groups to subgenomes and demonstrate the presence of chromosomal rearrangements. CONCLUSIONS: The paper combines GBS protocol modifications, a novel flexible GBS analysis pipeline, UGbS-Flex, recommendations to maximize SNP identification, updated genetic mapping software, and the first high-density maps of finger millet. The modules used in the UGbS-Flex pipeline and for genetic mapping were applied to finger millet, an allotetraploid selfing species without a reference genome, as a case study. The UGbS-Flex modules, which can be run independently, are easily transferable to species with other breeding systems or ploidy levels.

Development of Transcriptomic Markers for Population Analysis Using Restriction Site Associated RNA Sequencing (RARseq).

We describe restriction site associated RNA sequencing (RARseq), an RNAseq-based genotype by sequencing (GBS) method. It includes the construction of RNAseq libraries from double stranded cDNA digested with selected restriction enzymes. To test this, we constructed six single- and six-dual-digested RARseq libraries from six F2 pitcher plant individuals and sequenced them on a half of a Miseq run. On average, the de novo approach of population genome analysis detected 544 and 570 RNA SNPs, whereas the reference transcriptome-based approach revealed an average of 1907 and 1876 RNA SNPs per individual, from single- and dual-digested RARseq data, respectively. The average numbers of RNA SNPs and alleles per loci are 1.89 and 2.17, respectively. Our results suggest that the RARseq protocol allows good depth of coverage per loci for detecting RNA SNPs and polymorphic loci for population genomics and mapping analyses. In non-model systems where complete genomes sequences are not always available, RARseq data can be analyzed in reference to the transcriptome. In addition to enriching for functional markers, this method may prove particularly useful in organisms where the genomes are not favorable for DNA GBS.

Species tree estimation of diploid Helianthus (Asteraceae) using target enrichment.

PREMISE OF THE STUDY: The sunflower genus Helianthus has long been recognized as economically significant, containing species of agricultural and horticultural importance. Additionally, this genus displays a large range of phenotypic and genetic variation, making Helianthus a useful system for studying evolutionary and ecological processes. Here we present the most robust Helianthus phylogeny to date, laying the foundation for future studies of this genus. METHODS: We used a target enrichment approach across 37 diploid Helianthus species/subspecies with a total of 103 accessions. This technique garnered 170 genes used for both coalescent and concatenation analyses. The resulting phylogeny was additionally used to examine the evolution of life history and growth form across the genus. KEY RESULTS: Coalescent and concatenation approaches were largely congruent, resolving a large annual clade and two large perennial clades. However, several relationships deeper within the phylogeny were more weakly supported and incongruent among analyses including the placement of H. agrestis, H. cusickii, H. gracilentus, H. mollis, and H. occidentalis. CONCLUSIONS: The current phylogeny supports three major clades including a large annual clade, a southeastern perennial clade, and another clade of primarily large-statured perennials. Relationships among taxa are more consistent with early phylogenies of the genus using morphological and crossing data than recent efforts using single genes, which highlight the difficulties of phylogenetic estimation in genera known for reticulate evolution. Additionally, conflict and low support at the base of the perennial clades may suggest a rapid radiation and/or ancient introgression within the genus.

Accurate prediction of RNA nucleotide interactions with backbone k-tree model.

MOTIVATION: Given the importance of non-coding RNAs to cellular regulatory functions, it would be highly desirable to have accurate computational prediction of RNA 3D structure, a task which remains challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to achieve computational feasibility. However, native conformations may not be examined and prediction accuracy may be compromised due to sampling. State-of-the-art methods have yet to deliver satisfactory predictions for RNAs of length beyond 50 nucleotides. RESULTS: This paper presents a method to tackle a key step in the RNA 3D structure prediction problem, the prediction of the nucleotide interactions that constitute the desired 3D structure. The research is based on a novel graph model, called a backbone k-tree, to tightly constrain the nucleotide interaction relationships considered for RNA 3D structures. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions (including the non-canonical interactions in all recently revealed families) from the query sequence along with known or predicted canonical basepairs. The preliminary results indicate that in most cases the new method can predict with a high accuracy the nucleotide interactions that constitute the 3D structure of the query sequence. It thus provides a useful tool for the accurate prediction of RNA 3D structure. AVAILABILITY AND IMPLEMENTATION: The source package for BkTree is available at http://rna-informatics.uga.edu/index.php?f=software&p=BkTree. CONTACT: lding@uga.edu or cai@cs.uga.edu SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Resolving phylogenetic relationships of the recently radiated carnivorous plant genus Sarracenia using target enrichment.

The North American carnivorous pitcher plant genus Sarracenia (Sarraceniaceae) is a relatively young clade (<3 million years ago) displaying a wide range of morphological diversity in complex trapping structures. This recently radiated group is a promising system to examine the structural evolution and diversification of carnivorous plants; however, little is known regarding evolutionary relationships within the genus. Previous attempts at resolving the phylogeny have been unsuccessful, most likely due to few parsimony-informative sites compounded by incomplete lineage sorting. Here, we applied a target enrichment approach using multiple accessions to assess the relationships of Sarracenia species. This resulted in 199 nuclear genes from 75 accessions covering the putative 8-11 species and 8 subspecies/varieties. In addition, we recovered 42kb of plastome sequence from each accession to estimate a cpDNA-derived phylogeny. Unsurprisingly, the cpDNA had few parsimony-informative sites (0.5%) and provided little information on species relationships. In contrast, use of the targeted nuclear loci in concatenation and coalescent frameworks elucidated many relationships within Sarracenia even with high heterogeneity among gene trees. Results were largely consistent for both concatenation and coalescent approaches. The only major disagreement was with the placement of the purpurea complex. Moreover, results suggest an Appalachian massif biogeographic origin of the genus. Overall, this study highlights the utility of target enrichment using multiple accessions to resolve relationships in recently radiated taxa.

Information-theoretic uncertainty of SCFG-modeled folding space of the non-coding RNA.

UNLABELLED: RNA secondary structure ensembles define probability distributions for alternative equilibrium secondary structures of an RNA sequence. Shannon's entropy is a measure for the amount of diversity present in any ensemble. In this work, Shannon's entropy of the SCFG ensemble on an RNA sequence is derived and implemented in polynomial time for both structurally ambiguous and unambiguous grammars. Micro RNA sequences generally have low folding entropy, as previously discovered. Surprisingly, signs of significantly high folding entropy were observed in certain ncRNA families. More effective models coupled with targeted randomization tests can lead to a better insight into folding features of these families. AVAILABILITY: URL http://www.plantbio.uga.edu/~russell/index.php?s=1&n=5&r=0.

TRFolder-W: a web server for telomerase RNA structure prediction in yeast genomes.

UNLABELLED: TRFolder-W is a web server capable of predicting core structures of telomerase RNA (TR) in yeast genomes. TRFolder is a command-line Python toolkit for TR-specific structure prediction. We developed a web-version built on the django web framework, leveraging the work done previously, to include enhancements to increase flexibility of usage. To date, there are five core sub-structures commonly found in TR of fungal species, which are the template region, downstream pseudoknot, boundary element, core-closing stem and triple helix. The aim of TRFolder-W is to use the five core structures as fundamental units to predict potential TR genes for yeast, and to provide a user-friendly interface. Moreover, the application of TRFolder-W can be extended to predict the characteristic structure on species other than fungal species. AVAILABILITY: The web server TRFolder-W is available at http://rna-informatics.uga.edu/?f=software&p=TRFolder-w.

Longitudinal trends in climate drive flowering time clines in North American Arabidopsis thaliana.

Introduced species frequently show geographic differentiation, and when differentiation mirrors the ancestral range, it is often taken as evidence of adaptive evolution. The mouse-ear cress (Arabidopsis thaliana) was introduced to North America from Eurasia 150-200 years ago, providing an opportunity to study parallel adaptation in a genetic model organism. Here, we test for clinal variation in flowering time using 199 North American (NA) accessions of A. thaliana, and evaluate the contributions of major flowering time genes FRI, FLC, and PHYC as well as potential ecological mechanisms underlying differentiation. We find evidence for substantial within population genetic variation in quantitative traits and flowering time, and putatively adaptive longitudinal differentiation, despite low levels of variation at FRI, FLC, and PHYC and genome-wide reductions in population structure relative to Eurasian (EA) samples. The observed longitudinal cline in flowering time in North America is parallel to an EA cline, robust to the effects of population structure, and associated with geographic variation in winter precipitation and temperature. We detected major effects of FRI on quantitative traits associated with reproductive fitness, although the haplotype associated with higher fitness remains rare in North America. Collectively, our results suggest the evolution of parallel flowering time clines through novel genetic mechanisms.

Stable stem enabled Shannon entropies distinguish non-coding RNAs from random backgrounds.

BACKGROUND: The computational identification of RNAs in genomic sequences requires the identification of signals of RNA sequences. Shannon base pairing entropy is an indicator for RNA secondary structure fold certainty in detection of structural, non-coding RNAs (ncRNAs). Under the Boltzmann ensemble of secondary structures, the probability of a base pair is estimated from its frequency across all the alternative equilibrium structures. However, such an entropy has yet to deliver the desired performance for distinguishing ncRNAs from random sequences. Developing novel methods to improve the entropy measure performance may result in more effective ncRNA gene finding based on structure detection. RESULTS: This paper shows that the measuring performance of base pairing entropy can be significantly improved with a constrained secondary structure ensemble in which only canonical base pairs are assumed to occur in energetically stable stems in a fold. This constraint actually reduces the space of the secondary structure and may lower the probabilities of base pairs unfavorable to the native fold. Indeed, base pairing entropies computed with this constrained model demonstrate substantially narrowed gaps of Z-scores between ncRNAs, as well as drastic increases in the Z-score for all 13 tested ncRNA sets, compared to shuffled sequences. CONCLUSIONS: These results suggest the viability of developing effective structure-based ncRNA gene finding methods by investigating secondary structure ensembles of ncRNAs.

Mutational patterns in RNA secondary structure evolution examined in three RNA families.

The goal of this work was to study mutational patterns in the evolution of RNA secondary structure. We analyzed bacterial tmRNA, RNaseP and eukaryotic telomerase RNA secondary structures, mapping structural variability onto phylogenetic trees constructed primarily from rRNA sequences. We found that secondary structures evolve both by whole stem insertion/deletion, and by mutations that create or disrupt stem base pairing. We analyzed the evolution of stem lengths and constructed substitution matrices describing the changes responsible for the variation in the RNA stem length. In addition, we used principal component analysis of the stem length data to determine the most variable stems in different families of RNA. This data provides new insights into the evolution of RNA secondary structures and patterns of variation in the lengths of double helical regions of RNA molecules. Our findings will facilitate design of improved mutational models for RNA structure evolution.

Transcriptome analysis of sarracenia, an insectivorous plant.

Sarracenia species (pitcher plants) are carnivorous plants which obtain a portion of their nutrients from insects captured in the pitchers. To investigate these plants, we sequenced the transcriptome of two species, Sarracenia psittacina and Sarracenia purpurea, using Roche 454 pyrosequencing technology. We obtained 46 275 and 36 681 contigs by de novo assembly methods for S. psittacina and S. purpurea, respectively, and further identified 16 163 orthologous contigs between them. Estimation of synonymous substitution rates between orthologous and paralogous contigs indicates the events of genome duplication and speciation within the Sarracenia genus both occurred ∼2 million years ago. The ratios of synonymous and non-synonymous substitution rates indicated that 491 contigs have been under positive selection (K(a)/K(s) > 1). Significant proportions of these contigs were involved in functions related to binding activity. We also found that the greatest sequence similarity for both of these species was to Vitis vinifera, which is most consistent with a non-current classification of the order Ericales as an asterid. This study has provided new insights into pitcher plants and will contribute greatly to future research on this genus and its distinctive ecological adaptations.

Analyzing modular RNA structure reveals low global structural entropy in microRNA sequence.

Secondary structure remains the most exploitable feature for noncoding RNA (ncRNA) gene finding in genomes. However, methods based on secondary structure prediction may generate superfluous amount of candidates for validation and have yet to deliver the desired performance that can complement experimental efforts in ncRNA gene finding. This paper investigates a novel method, unpaired structural entropy (USE) as a measurement for the structure fold stability of ncRNAs. USE proves to be effective in identifying from the genome background a class of ncRNAs, such as precursor microRNAs (pre-miRNAs) that contains a long stem hairpin loop. USE correlates well and performs better than other measures on pre-miRNAs, including the previously formulated structural entropy. As an SVM classifier, USE outperforms existing pre-miRNA classifiers. A long stem hairpin loop is common for a number of other functional RNAs including introns splicing hairpins loops and intrinsic termination hairpin loops. We believe USE can be further applied in developing ab initio prediction programs for a larger class of ncRNAs.

TRFolder: computational prediction of novel telomerase RNA structures in yeast genomes.

The identification of Telomerase RNAs (TRs) has been difficult owing to their rapid evolutionary divergence. The common core structure found in all known TRs contains a pseudoknot and a triple helix, which are beyond the capability of existing RNA-structure-profiling techniques. We describe a novel approach to predict the structure of key TR features and to aid the identification of TRs in genomes, using a program we developed, TRFolder. We applied our method to confirm and improve previously studied core structures from Saccharomyces and Kluyveromyces TRs. We made novel structural predictions of core elements of the TRs from Schizosaccharomyces pombe, Candida albicans, and several other yeast species.

Development and characterization of microsatellite markers in Sarracenia L. (pitcher plant) species.

Sarracenia species (pitcher plants) are carnivorous plants which obtain a portion of their nutrients from insects captured in the pitchers. Sarracenia species naturally hybridize with each other, and hybrid swarms have been identified. A number of the taxa within the genus are considered endangered. In order to facilitate evolutionary, ecological and conservation genetic analyses within the genus, we developed 25 microsatellite loci which show variability either within species or between species. Three S. purpurea populations were examined with 10 primer sets which showed within population variability.

RNApasta: a tool for analysis of RNA structural alignments.

The study of RNA sequence structural alignments has become an important part of characterising noncoding RNAs. We developed RNApasta, a Java program with a graphical interface, to perform analysis and editing of RNA alignments. RNApasta can be used to generate statistics for modelling RNAs and to develop homogeneous subsets of alignments that contain variability. RNApasta includes several functions to characterise variation in stem and loop lengths, including phylogenetic analysis of this variation; as an example, we analyse variation in mir-31 pre-microRNA loop length variation, demonstrating that the sequences with longer loops had a single evolutionary origin.

RNATOPS-W: a web server for RNA structure searches of genomes.

RNATOPS-W is a web server to search sequences for RNA secondary structures including pseudoknots. The server accepts an annotated RNA multiple structural alignment as a structural profile and genomic or other sequences to search. It is built upon RNATOPS, a command line C++ software package for the same purpose, in which filters to speed up search are manually selected. RNATOPS-W improves upon RNATOPS by adding the function of automatic selection of a hidden Markov model (HMM) filter and also a friendly user interface for selection of a substructure filter by the user. In addition, RNATOPS-W complements existing RNA secondary structure search web servers that either use built-in structure profiles or are not able to detect pseudoknots. RNATOPS-W inherits the efficiency of RNATOPS in detecting large, complex RNA structures.

Fast and accurate search for non-coding RNA pseudoknot structures in genomes.

MOTIVATION: Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal for bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, the computational difficulty in aligning an RNA sequence to a pseudoknot has prohibited fast and accurate search of arbitrary RNA structures. Our previous work introduced a graph model for RNA pseudoknots and proposed to solve the structure-sequence alignment by graph optimization. Given k candidate regions in the target sequence for each of the n stems in the structure, we could compute a best alignment in time O(k(t)n) based upon a tree width t decomposition of the structure graph. However, to implement this method to programs that can routinely perform fast yet accurate RNA pseudoknot searches, we need novel heuristics to ensure that, without degrading the accuracy, only a small number of stem candidates need to be examined and a tree decomposition of a small tree width can always be found for the structure graph. RESULTS: The current work builds on the previous one with newly developed preprocessing algorithms to reduce the values for parameters k and t and to implement the search method into a practical program, called RNATOPS, for RNA pseudoknot search. In particular, we introduce techniques, based on probabilistic profiling and distance penalty functions, which can identify for every stem just a small number k (e.g. k