Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Accuracy assessment of depth estimates from variation in pre- and post-processing of multi-beam SONAR surveys in a fjord environment

Senior thesis written for Oceanography 445

Nop53p interacts with 5.8S rRNA co-transcriptionally, and regulates processing of pre-rRNA by the exosome

In eukaryotes, pre-rRNA processing depends on a large number of nonribosomal trans-acting factors that form intriguingly organized complexes. One of the early stages of pre-rRNA processing includes formation of the two intermediate complexes pre-40S and pre-60S, which then form the mature ribosome subunits. Each of these complexes contains specific pre-rRNAs, ribosomal proteins and processing factors. The yeast nucleolar protein Nop53p has previously been identified in the pre-60S complex and shown to affect pre-rRNA processing by directly binding to 5.8S rRNA, and to interact with Nop17p and Nip7p, which are also involved in this process. Here we show that Nop53p binds 5.8S rRNA co-transcriptionally through its N-terminal region, and that this protein portion can also partially complement growth of the conditional mutant strain Delta nop53/GAL:NOP53. Nop53p interacts with Rrp6p and activates the exosome in vitro. These results indicate that Nop53p may recruit the exosome to 7S pre-rRNA for processing. Consistent with this observation and similar to the observed in exosome mutants, depletion of Nop53p leads to accumulation of polyadenylated pre-rRNAs.

Utp25p, a nucleolar Saccharomyces cerevisiae protein, interacts with U3 snoRNP subunits and affects processing of the 35S pre-rRNA

In eukaryotes, pre-rRNA processing depends on a large number of nonribosomal trans-acting factors that form intriguingly organized complexes. Two intermediate complexes, pre-40S and pre-60S, are formed at the early stages of 35S pre-rRNA processing and give rise to the mature ribosome subunits. Each of these complexes contains specific pre-rRNAs, some ribosomal proteins and processing factors. The novel yeast protein Utp25p has previously been identified in the nucleolus, an indication that this protein could be involved in ribosome biogenesis. Here we show that Utp25p interacts with the SSU processome proteins Sas10p and Mpp10p, and affects 18S rRNA maturation. Depletion of Utp25p leads to accumulation of the pre-rRNA 35S and the aberrant rRNA 23S, and to a severe reduction in 40S ribosomal subunit levels. Our results indicate that Utp25p is a novel SSU processome subunit involved in pre-40S maturation.

Footprints of a trypanosomatid RNA world: pre-small subunit rRNA processing by spliced leader addition trans-splicing

The addition of a capped mini-exon [spliced leader (SL)] through trans-splicing is essential for the maturation of RNA polymerase (pol) II-transcribed polycistronic pre-mRNAs in all members of the Trypanosomatidae family. This process is an inter-molecular splicing reaction that follows the same basic rules of cis-splicing reactions. In this study, we demonstrated that mini-exons were added to precursor ribosomal RNA (pre-rRNA) are transcribed by RNA pol I, including the 5' external transcribed spacer (ETS) region. Additionally, we detected the SL-5' ETS molecule using three distinct methods and located the acceptor site between two known 5' ETS rRNA processing sites (A' and A1) in four different trypanosomatids. Moreover, we detected a polyadenylated 5' ETS upstream of the trans-splicing acceptor site, which also occurs in pre-mRNA trans-splicing. After treatment with an indirect trans-splicing inhibitor (sinefungin), we observed SL-5' ETS decay. However, treatment with 5-fluorouracil (a precursor of RNA synthesis that inhibits the degradation of pre-rRNA) led to the accumulation of SL-5' ETS, suggesting that the molecule may play a role in rRNA degradation. The detection of trans-splicing in these molecules may indicate broad RNA-joining properties, regardless of the polymerase used for transcription.

Mammalian pre-mRNA 3' end processing factor CF I m 68 functions in mRNA export

Export of mRNA from the nucleus is linked to proper processing and packaging into ribonucleoprotein complexes. Although several observations indicate a coupling between mRNA 3' end formation and export, it is not known how these two processes are mechanistically connected. Here, we show that a subunit of the mammalian pre-mRNA 3' end processing complex, CF I(m)68, stimulates mRNA export. CF I(m)68 shuttles between the nucleus and the cytoplasm in a transcription-dependent manner and interacts with the mRNA export receptor NXF1/TAP. Consistent with the idea that CF I(m)68 may act as a novel adaptor for NXF1/TAP, we show that CF I(m)68 promotes the export of a reporter mRNA as well as of endogenous mRNAs, whereas silencing by RNAi results in the accumulation of mRNAs in the nucleus. Moreover, CF I(m)68 associates with 80S ribosomes but not polysomes, suggesting that it is part of the mRNP that is remodeled in the cytoplasm during the initial stages of translation. These results reveal a novel function for the pre-mRNA 3' end processing factor CF I(m)68 in mRNA export.

A 5'-3' exonuclease activity involved in forming the 3' products of histone pre-mRNA processing in vitro.

Histone RNA 3' processing in vitro produces one or more 5' cleavage products corresponding to the mature histone mRNA 3' end, and a group of 3' cleavage products whose 5' ends are mostly located several nucleotides downstream of the mRNA 3' end. The formation of these 3' products is coupled to the formation of 5' products and dependent on the U7 snRNP and a heat-labile processing factor. These short 3' products therefore are a true and general feature of the processing reaction. Identical 3' products are also formed from a model RNA containing all spacer nucleotides downstream of the mature mRNA 3' end, but no sequences from the mature mRNA. Again, this reaction is dependent on both the U7 snRNP and a heat-labile factor. Unlike the processing with a full-length histone pre-mRNA, this reaction produces only 3' but no 5' fragments. In addition, product formation is inhibited by addition of cap structures at the model RNA 5' end, indicating that product formation occurs by 5'-3' exonucleolytic degradation. This degradation of a model 3' product by a 5'-3' exonuclease suggests a mechanism for the release of the U7 snRNP after processing by shortening the cut-off histone spacer sequences base paired to U7 RNA.

3' end processing of mouse histone pre-mRNA: evidence for additional base-pairing between U7 snRNA and pre-mRNA.

We have analysed the extent of base-pairing interactions between spacer sequences of histone pre-mRNA and U7 snRNA present in the trans-acting U7 snRNP and their importance for histone RNA 3' end processing in vitro. For the efficiently processed mouse H4-12 gene, a computer analysis revealed that additional base pairs could be formed with U7 RNA outside of the previously recognised spacer element (stem II). One complementarity (stem III) is located more 3' and involves nucleotides from the very 5' end of U7 RNA. The other, more 5' located complementarity (stem I) involves nucleotides of the Sm binding site of U7 RNA, a part known to interact with snRNP structural proteins. These potential stem structures are separated from each other by short internal loops of unpaired nucleotides. Mutational analyses of the pre-mRNA indicate that stems II and III are equally important for interaction with the U7 snRNP and for processing, whereas mutations in stem I have moderate effects on processing efficiency, but do not impair complex formation with the U7 snRNP. Thus nucleotides near the processing site may be important for processing, but do not contribute to the assembly of an active complex by forming a stem I structure. The importance of stem III was confirmed by the ability of a complementary mutation in U7 RNA to suppress a stem III mutation in a complementation assay using Xenopus laevis oocytes. The main role of the factor(s) binding to the upstream hairpin loop is to stabilise the U7-pre-mRNA complex. This was shown by either stabilising (by mutation) or destabilising (by increased temperature) the U7-pre-mRNA base-pairing under conditions where hairpin factor binding was either allowed or prevented (by mutation or competition). The hairpin dependence of processing was found to be inversely related to the strength of the U7-pre-mRNA interaction.

Variable effects of the conserved RNA hairpin element upon 3' end processing of histone pre-mRNA in vitro.

We have studied the requirements for efficient histone-specific RNA 3' processing in nuclear extract from mammalian tissue culture cells. Processing is strongly impaired by mutations in the pre-mRNA spacer element that reduce the base-pairing potential with U7 RNA. Moreover, by exchanging the hairpin and spacer elements of two differently processed H4 genes, we find that this difference is exclusively due to the spacer element. Finally, processing is inhibited by the addition of competitor RNAs, if these contain a wild-type spacer sequence, but not if their spacer element is mutated. Conversely, the importance of the hairpin for histone RNA 3' processing is highly variable: A hairpin mutant of the H4-12 gene is processed with almost wild-type efficiency in extract from K21 mouse mastocytoma cells but is strongly affected in HeLa cell extract, whereas an identical hairpin mutant of the H4-1 gene is affected in both extracts. The hairpin defect of H4-12-specific RNA in HeLa cells can be overcome by a compensatory mutation that increases the base complementarity to U7 snRNA. Very similar results were also obtained in RNA competition experiments: processing of H4-12-specific RNA can be competed by RNA carrying a wild-type hairpin element in extract from HeLa, but not K21 cells, whereas processing of H4-1-specific RNA can be competed in both extracts. With two additional histone genes we obtained results that were in one case intermediate and in the other similar to those obtained with H4-1. These results suggest that hairpin binding factor(s) can cooperatively support the ability of U7 snRNPs to form an active processing complex, but is(are) not directly involved in the processing mechanism.

Participation of the nuclear cap binding complex in pre-mRNA 3′ processing

Communication between the 5′ and 3′ ends is a common feature of several aspects of eukaryotic mRNA metabolism. In the nucleus, the pre-mRNA 5′ end is bound by the nuclear cap binding complex (CBC). This RNA–protein complex plays an active role in both splicing and RNA export. We provide evidence for participation of CBC in the processing of the 3′ end of the message. Depletion of CBC from HeLa cell nuclear extract strongly reduced the endonucleolytic cleavage step of the cleavage and polyadenylation process. Cleavage was restored by addition of recombinant CBC. CBC depletion was found to reduce the stability of poly(A) site cleavage complexes formed in nuclear extract. We also provide evidence that the communication between the 5′ and 3′ ends of the pre-mRNA during processing is mediated by the physical association of the CBC/cap complex with 3′ processing factors bound at the poly(A) site. These observations, along with previous data on the function of CBC in splicing, illustrate the key role played by CBC in pre-mRNA recognition and processing. The data provides further support for the hypothesis that pre-mRNAs and mRNAs may exist and be functional in the form of “closed-loops,” due to interactions between factors bound at their 5′ and 3′ ends.

Partially Processed pre-rRNA Is Preserved in Association with Processing Components in Nucleolus-derived Foci during Mitosis

Previous studies showed that components implicated in pre-rRNA processing, including U3 small nucleolar (sno)RNA, fibrillarin, nucleolin, and proteins B23 and p52, accumulate in perichromosomal regions and in numerous mitotic cytoplasmic particles, termed nucleolus-derived foci (NDF) between early anaphase and late telophase. The latter structures were analyzed for the presence of pre-rRNA by fluorescence in situ hybridization using probes for segments of pre-rRNA with known half-lives. The NDF did not contain the short-lived 5′-external transcribed spacer (ETS) leader segment upstream from the primary processing site in 47S pre-rRNA. However, the NDF contained sequences from the 5′-ETS core, 18S, internal transcribed spacer 1 (ITS1), and 28S segments and also had detectable, but significantly reduced, levels of the 3′-ETS sequence. Northern analyses showed that in mitotic cells, the latter sequences were present predominantly in 45S-46S pre-rRNAs, indicating that high-molecular weight processing intermediates are preserved during mitosis. Two additional essential processing components were also found in the NDF: U8 snoRNA and hPop1 (a protein component of RNase MRP and RNase P). Thus, the NDF appear to be large complexes containing partially processed pre-rRNA associated with processing components in which processing has been significantly suppressed. The NDF may facilitate coordinated assembly of postmitotic nucleoli.

Phosphoinositide Signaling Pathways in Nuclei Are Associated with Nuclear Speckles Containing Pre-mRNA Processing Factors

Phosphoinositide signal transduction pathways in nuclei use enzymes that are indistinguishable from their cytosolic analogues. We demonstrate that distinct phosphatidylinositol phosphate kinases (PIPKs), the type I and type II isoforms, are concentrated in nuclei of mammalian cells. The cytosolic and nuclear PIPKs display comparable activities toward the substrates phosphatidylinositol 4-phosphate and phosphatidylinositol 3-phosphate. Indirect immunofluorescence revealed that these kinases were associated with distinct subnuclear domains, identified as “nuclear speckles,” which also contained pre-mRNA processing factors. A pool of nuclear phosphatidylinositol bisphosphate (PIP2), the product of these kinases, was also detected at these same sites by monoclonal antibody staining. The localization of PIPKs and PIP2 to speckles is dynamic in that both PIPKs and PIP2 reorganize along with other speckle components upon inhibition of mRNA transcription. Because PIPKs have roles in the production of most phosphatidylinositol second messengers, these findings demonstrate that phosphatidylinositol signaling pathways are localized at nuclear speckles. Surprisingly, the PIPKs and PIP2 are not associated with invaginations of the nuclear envelope or any nuclear membrane structure. The putative absence of membranes at these sites suggests novel mechanisms for the generation of phosphoinositides within these structures.

Functional separation of pre-rRNA processing steps revealed by truncation of the U3 small nucleolar ribonucleoprotein component, Mpp10

The U3 small nucleolar ribonucleoprotein (snoRNP) is required for three cleavage events that generate the mature 18S rRNA from the pre-rRNA. In Saccharomyces cerevisiae, depletion of Mpp10, a U3 snoRNP-specific protein, halts 18S rRNA production and impairs cleavage at the three U3 snoRNP-dependent sites: A0, A1, and A2. We have identified truncation mutations of Mpp10 that affect 18S rRNA synthesis and confer cold-sensitivity and slow growth. However, distinct from yeast cells depleted of Mpp10, the mutants carrying these truncated Mpp10 proteins accumulate a novel precursor, resulting from cleavage at only A0. The Mpp10 truncations do not alter association of Mpp10 with the U3 snoRNA, nor do they affect snoRNA or protein stability. Thus, the role in processing of the U3 snoRNP can be separated into cleavage at the A0 site, which occurs in the presence of truncated Mpp10, and cleavage at the A1/A2 sites, which occurs only with intact Mpp10. These results strongly argue for a role for Mpp10 in processing at the A1/A2 sites.

RNA editing activity is associated with splicing factors in lnRNP particles: The nuclear pre-mRNA processing machinery

Multiple members of the ADAR (adenosine deaminases acting on RNA) gene family are involved in A-to-I RNA editing. It has been speculated that they may form a large multicomponent protein complex. Possible candidates for such complexes are large nuclear ribonucleoprotein (lnRNP) particles. The lnRNP particles consist mainly of four spliceosomal subunits that assemble together with the pre-mRNA to form a large particle and thus are viewed as the naturally assembled pre-mRNA processing machinery. Here we investigated the presence of ADARs in lnRNP particles by Western blot analysis using anti-ADAR antibodies and by indirect immunoprecipitation. Both ADAR1 and ADAR2 were found associated with the spliceosomal components Sm and SR proteins within the lnRNP particles. The two ADARs, associated with lnRNP particles, were enzymatically active in site-selective A-to-I RNA editing. We demonstrate the association of ADAR RNA editing enzymes with physiological supramolecular complexes, the lnRNP particles.