Minimotif miner 2nd release: a database and web system for motif search.

Minimotif Miner (MnM) consists of a minimotif database and a web-based application that enables prediction of motif-based functions in user-supplied protein queries. We have revised MnM by expanding the database more than 10-fold to approximately 5000 motifs and standardized the motif function definitions. The web-application user interface has been redeveloped with new features including improved navigation, screencast-driven help, support for alias names and expanded SNP analysis. A sample analysis of prion shows how MnM 2 can be used. Weblink: http://mnm.engr.uconn.edu, weblink for version 1 is http://sms.engr.uconn.edu.

Fast and practical algorithms for planted (l, d) motif search.

We consider the planted (l, d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s1, . . . , sn} with up to d errors, a problem that arises from the need to find transcription factor-binding sites in genomic information. We propose a sequence of practical algorithms, which start based on the ideas considered in PMS1. These algorithms are exact, have little space requirements, and are able to tackle challenging instances with bigger d, taking less time in the instances reported solved by exact algorithms. In particular, one of the proposed algorithms, PMSprune, is able to solve the challenging instances, such as (17, 6) and (19, 7), which were not previously reported as solved in the literature.

An efficient algorithm for minimum degeneracy primer selection.

Selecting degenerate primers for multiplex polymerase chain reaction (MP-PCR) experiments, called the degenerate primer design problem (DPDP), is an important problem in computational molecular biology and has drawn the attention of numerous researchers in the recent past. Several variants of DPDP were formulated by Linhart and Shamir and proven to be NP-complete. A number of algorithms have been proposed for one such variant, namely, the maximum coverage degenerate primer design problem (MC-DPDP). In this paper, we consider another important variant called the minimum degeneracy degenerate primer design with errors problem (MD-DPDEP), propose an algorithm to design a degenerate primer of minimum degeneracy for a given set of DNA sequences and show experimental results of its performance on random and real biological datasets. Our algorithm combines methodologies in motif discovery and an iterative technique to design the primer.

A broadly conserved pathway generates 3'UTR-directed primary piRNAs.

BACKGROUND: Piwi-interacting RNAs (piRNAs) are approximately 24-30 nucleotide regulatory RNAs that are abundant in animal gonads and early embryos. The best-characterized piRNAs mediate a conserved pathway that restricts transposable elements, and these frequently engage a "ping-pong" amplification loop. Certain stages of mammalian testis also accumulate abundant piRNAs of unknown function, which derive from noncoding RNAs that are depleted in transposable element content and do not engage in ping-pong. RESULTS: We report that the 3' untranslated regions (3'UTRs) of an extensive set of messenger RNAs (mRNAs) are processed into piRNAs in Drosophila ovaries, murine testes, and Xenopus eggs. Analysis of different mutants and Piwi-class immunoprecipitates indicates that their biogenesis depends on primary piRNA components, but not most ping-pong components. Several observations suggest that mRNAs are actively selected for piRNA production for regulatory purposes. First, genic piRNAs do not accumulate in proportion to the level of their host transcripts, and many highly expressed transcripts lack piRNAs. Second, piRNA-producing mRNAs in Drosophila and mouse are enriched for specific gene ontology categories distinct from those of simply abundant transcripts. Third, the protein output of traffic jam, whose 3'UTR generates abundant piRNAs, is increased in piwi mutant follicle clones. CONCLUSIONS: We reveal a conserved primary piRNA pathway that selects and metabolizes the 3'UTRs of a broad set of cellular transcripts, probably for regulatory purposes. These findings strongly increase the breadth of Argonaute-mediated small RNA systems in metazoans.

Two distinct mechanisms generate endogenous siRNAs from bidirectional transcription in Drosophila melanogaster.

Cis-natural antisense transcripts (cis-NATs) have been speculated to be substrates for endogenous RNA interference (RNAi), but little experimental evidence for such a pathway in animals has been reported. Analysis of massive Drosophila melanogaster small RNA data sets now reveals two mechanisms that yield endogenous small interfering RNAs (siRNAs) via bidirectional transcription. First, >100 cis-NATs with overlapping 3' exons generate 21-nt, and, based on previously published small RNA data [corrected] Dicer-2 (Dcr-2)-dependent, 3'-end modified siRNAs. The processing of cis-NATs by RNA interference (RNAi) seems to be actively restricted, and the selected loci are enriched for nucleic acid-based functions and include Argonaute-2 (AGO2) itself. Second, we report that extended intervals of the thickveins and klarsicht genes generate exceptionally abundant siRNAs from both strands. These siRNA clusters derive from atypical cis-NAT arrangements involving introns and 5' or internal exons, but their biogenesis is similarly Dcr-2- and AGO2-dependent. These newly recognized siRNA pathways broaden the scope of regulatory networks mediated by small RNAs.

Minimotif Miner: a tool for investigating protein function.

In addition to large domains, many short motifs mediate functional post-translational modification of proteins as well as protein-protein interactions and protein trafficking functions. We have constructed a motif database comprising 312 unique motifs and a web-based tool for identifying motifs in proteins. Functional motifs predicted by MnM can be ranked by several approaches, and we validated these scores by analyzing thousands of confirmed examples and by confirming prediction of previously unidentified 14-3-3 motifs in EFF-1.

High-performance exact algorithms for motif search.

OBJECTIVE: The human genome project has resulted in the generation of voluminous biological data. Novel computational techniques are called for to extract useful information from this data. One such technique is that of finding patterns that are repeated over many sequences (and possibly over many species). In this paper we study the problem of identifying meaningful patterns (i.e., motifs) from biological data, the motif search problem. METHODS: The general version of the motif search problem is NP-hard. Numerous algorithms have been proposed in the literature to solve this problem. Many of these algorithms fall under the category of heuristics. We concentrate on exact algorithms in this paper. In particular, we concentrate on two different versions of the motif search problem and offer exact algorithms for them. RESULTS: In this paper we present algorithms for two versions of the motif search problem. All of our algorithms are elegant and use only such simple data structures as arrays. For the first version of the problem described as Problem 1 in the paper, we present a simple sorting based algorithm, SMS (Simple Motif Search). This algorithm has been coded and experimental results have been obtained. For the second version of the problem (described in the paper as Problem 2), we present two different algorithms--a deterministic algorithm (called DMS) and a randomized algorithm (Monte Carlo algorithm). We also show how these algorithms can be parallelized. CONCLUSIONS: All the algorithms proposed in this paper are improvements over existing algorithms for these versions of motif search in biological sequence data. The algorithms presented have the potential of performing well in practice.