In Silico analysis of the sequence and structure of plant microRNAs packaged in extracellular vesicles.

Small RNA (sRNA)-mediated RNA interference (RNAi) is a conserved eukaryotic cellular process associated with immune defense and pathogen virulence. The cross-kingdom transfer of noncoding regulatory sRNAs between host and pathogen can be mediated via lipid, membrane-bound extracellular vesicles (EVs). Several studies have reported in mammalian and plant systems there is selective packaging of sRNAs into EVs. In mammals, sequence patterns and structural motifs are implicated in signaling pathways related to EV cargo sorting. However, in the emerging plant EV field, there is a lack of knowledge of the mechanisms involved in selecting sRNAs for EV transport. In this study, we accessed publicly available databases where the sRNA content of plant EVs has been characterized from control plants and those released in response to fungal pathogen infection. An in-depth analysis revealed 158 sRNAs are EV packaged, with ∼60 % sharing a sequence motif and 98.1 % forming a secondary hairpin stem-loop structure. Many of the predicted plant targets for the EV sRNAs were associated with biological pathways involved in metabolism and regulation processes. Overall, our in silico analysis of sRNAs packaged in plant EVs highlight that a computational approach can offer valuable insights into the cross-kingdom EV transport of sRNAs.

Consensus properties and their large-scale applications for the gene duplication problem.

Solving the gene duplication problem is a classical approach for species tree inference from gene trees that are confounded by gene duplications. This problem takes a collection of gene trees and seeks a species tree that implies the minimum number of gene duplications. Wilkinson et al. posed the conjecture that the gene duplication problem satisfies the desirable Pareto property for clusters. That is, for every instance of the problem, all clusters that are commonly present in the input gene trees of this instance, called strict consensus, will also be found in every solution to this instance. We prove that this conjecture does not generally hold. Despite this negative result we show that the gene duplication problem satisfies a weaker version of the Pareto property where the strict consensus is found in at least one solution (rather than all solutions). This weaker property contributes to our design of an efficient scalable algorithm for the gene duplication problem. We demonstrate the performance of our algorithm in analyzing large-scale empirical datasets. Finally, we utilize the algorithm to evaluate the accuracy of standard heuristics for the gene duplication problem using simulated datasets.

Consensus properties for the deep coalescence problem and their application for scalable tree search.

BACKGROUND: To infer a species phylogeny from unlinked genes, phylogenetic inference methods must confront the biological processes that create incongruence between gene trees and the species phylogeny. Intra-specific gene variation in ancestral species can result in deep coalescence, also known as incomplete lineage sorting, which creates incongruence between gene trees and the species tree. One approach to account for deep coalescence in phylogenetic analyses is the deep coalescence problem, which takes a collection of gene trees and seeks the species tree that implies the fewest deep coalescence events. Although this approach is promising for phylogenetics, the consensus properties of this problem are mostly unknown and analyses of large data sets may be computationally prohibitive. RESULTS: We prove that the deep coalescence consensus tree problem satisfies the highly desirable Pareto property for clusters (clades). That is, in all instances, each cluster that is present in all of the input gene trees, called a consensus cluster, will also be found in every optimal solution. Moreover, we introduce a new divide and conquer method for the deep coalescence problem based on the Pareto property. This method refines the strict consensus of the input gene trees, thereby, in practice, often greatly reducing the complexity of the tree search and guaranteeing that the estimated species tree will satisfy the Pareto property. CONCLUSIONS: Analyses of both simulated and empirical data sets demonstrate that the divide and conquer method can greatly improve upon the speed of heuristics that do not consider the Pareto consensus property, while also guaranteeing that the proposed solution fulfills the Pareto property. The divide and conquer method extends the utility of the deep coalescence problem to data sets with enormous numbers of taxa.

Triplet supertree heuristics for the tree of life.

BACKGROUND: There is much interest in developing fast and accurate supertree methods to infer the tree of life. Supertree methods combine smaller input trees with overlapping sets of taxa to make a comprehensive phylogenetic tree that contains all of the taxa in the input trees. The intrinsically hard triplet supertree problem takes a collection of input species trees and seeks a species tree (supertree) that maximizes the number of triplet subtrees that it shares with the input trees. However, the utility of this supertree problem has been limited by a lack of efficient and effective heuristics. RESULTS: We introduce fast hill-climbing heuristics for the triplet supertree problem that perform a step-wise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. To realize time efficient heuristics we designed the first nontrivial algorithms for two standard search problems, which greatly improve on the time complexity to the best known (naïve) solutions by a factor of n and n2 (the number of taxa in the supertree). These algorithms enable large-scale supertree analyses based on the triplet supertree problem that were previously not possible. We implemented hill-climbing heuristics that are based on our new algorithms, and in analyses of two published supertree data sets, we demonstrate that our new heuristics outperform other standard supertree methods in maximizing the number of triplets shared with the input trees. CONCLUSION: With our new heuristics, the triplet supertree problem is now computationally more tractable for large-scale supertree analyses, and it provides a potentially more accurate alternative to existing supertree methods.