Search

The faithful segregation of eukaryotic chromosomes in mitosis requires that the genome be duplicated completely prior to anaphase. However, cells with large genomes sometimes fail to complete replication during interphase and instead enter mitosis with regions of incompletely replicated DNA. These regions are processed in early mitosis via a process known as mitotic DNA repair synthesis (MiDAS), but little is known about how cells switch from conventional DNA replication to MiDAS. Using the early embryo of the nematode Caenorhabditis elegans as a model system, we show that the TRAIP ubiquitin ligase drives replisome disassembly in response to incomplete DNA replication, thereby providing access to replication forks for other factors. Moreover, TRAIP is essential for MiDAS in human cells, and is important in both systems to prevent mitotic segregation errors. Our data indicate that TRAIP is a master regulator of the processing of incomplete DNA replication during mitosis in metazoa.

We show, given a binary integer function diamond that is piecewise polynomial, that (+,diamond) vector products are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include the dominance and l_{2p+1} distances for constant p. Our results imply equivalence (up to polylog factors) between the complexity of computing All Pairs Hamming Distance, All Pairs l_{2p+1} Distance and Dominance Matrix Product, and equivalence between Hamming Distance Pattern Matching, l_{2p+1} Pattern Matching and Less-Than Pattern Matching. The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are likely to be optimal, given lack of progress in improving upper bounds for Hamming distance in the past 30 years. While reductions between selected pairs of products were presented in the past, our work is the first to generalize them to a general class of functions, showing that a wide class of "intermediate" complexity problems are in fact equivalent.

We show that a broad class of (+, diamond) vector products (for binary integer functions diamond) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Our results imply equivalence (up to poly log n factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. As a consequence, Yuster's (SODA'09) algorithm improves not only Matousek's (IPL'91), but also the results of Indyk, Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09). Furthermore, our reductions apply to the pattern matching setting, showing equivalence (up to poly log n factors) between pattern matching under Hamming Distance, l_{2p+1} Distance, Dominance Product and Threshold Product, with current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and Farach (Ann. Math. Artif. Intell.'91), Atallah and Duket (IPL'11), Clifford, Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05). The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are new. Additionally, we show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n x (n * d) and (n * d) x n, each with (n * d) non-zero entries. This means that the current upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse matrix multiplication algorithm by Yuster and Zwick (ACM TALG'05) and vice versa.

We show that a broad class of (+, diamond) vector products (for binary integer functions diamond) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Our results imply equivalence (up to poly log n factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. As a consequence, Yuster's (SODA'09) algorithm improves not only Matousek's (IPL'91), but also the results of Indyk, Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09). Furthermore, our reductions apply to the pattern matching setting, showing equivalence (up to poly log n factors) between pattern matching under Hamming Distance, l_{2p+1} Distance, Dominance Product and Threshold Product, with current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and Farach (Ann. Math. Artif. Intell.'91), Atallah and Duket (IPL'11), Clifford, Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05). The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are new. Additionally, we show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n x (n * d) and (n * d) x n, each with (n * d) non-zero entries. This means that the current upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse matrix multiplication algorithm by Yuster and Zwick (ACM TALG'05) and vice versa.

Deubiquitinating enzymes (DUBs) remove ubiquitin (Ub) from Ub-conjugated substrates to regulate the functional outcome of ubiquitylation. Here we report the discovery of a new family of DUBs, which we have named MINDY (motif interacting with Ub-containing novel DUB family). Found in all eukaryotes, MINDY-family DUBs are highly selective at cleaving K48-linked polyUb, a signal that targets proteins for degradation. We identify the catalytic activity to be encoded within a previously unannotated domain, the crystal structure of which reveals a distinct protein fold with no homology to any of the known DUBs. The crystal structure of MINDY-1 (also known as FAM63A) in complex with propargylated Ub reveals conformational changes that realign the active site for catalysis. MINDY-1 prefers cleaving long polyUb chains and works by trimming chains from the distal end. Collectively, our results reveal a new family of DUBs that may have specialized roles in regulating proteostasis.

The Hof1 protein (Homologue of Fifteen) regulates formation of the primary septum during cytokinesis in the budding yeast Saccharomyces cerevisiae, whereas the orthologous Cdc15 protein in fission yeast regulates the actomyosin ring by using its F-BAR domain to recruit actin nucleators to the cleavage site. Here we show that budding yeast Hof1 also contributes to actin ring assembly in parallel with the Rvs167 protein. Simultaneous deletion of the HOF1 and RVS167 genes is lethal, and cells fail to assemble the actomyosin ring as they progress through mitosis. Although Hof1 and Rvs167 are not orthologues, they both share an analogous structure, with an F-BAR or BAR domain at the amino terminus, capable of inducing membrane curvature, and SH3 domains at the carboxyl terminus that bind to specific proline-rich targets. The SH3 domain of Rvs167 becomes essential for assembly of the actomyosin ring in cells lacking Hof1, suggesting that it helps to recruit a regulator of the actin cytoskeleton. This new function of Rvs167 appears to be independent of its known role as a regulator of the Arp2/3 actin nucleator, as actin ring assembly is not abolished by the simultaneous inactivation of Hof1 and Arp2/3. Instead we find that recruitment to the bud-neck of the Iqg1 actin regulator is defective in cells lacking Hof1 and Rvs167, though future studies will be needed to determine if this reflects a direct interaction between these factors. The redundant role of Hof1 in actin ring assembly suggests that the mechanism of actin ring assembly has been conserved to a greater extent across evolution than anticipated previously. © 2013 Nkosi et al.

The chitin synthase that makes the primary septum during cell division in budding yeasts is an important therapeutic target with an unknown activation mechanism. We previously found that the C2-domain of the Saccharomyces cerevisiae Inn1 protein plays an essential but uncharacterised role at the cleavage site during cytokinesis. By combining a novel degron allele of INN1 with a point mutation in the C2-domain, we screened for mutations in other genes that suppress the resulting defect in cell division. In this way, we identified 22 dominant mutations of CHS2 (chitin synthase II) that map to two neighbouring sites in the catalytic domain. Chs2 in isolated cell membranes is normally nearly inactive (unless protease treatment is used to bypass inhibition); however, the dominant suppressor allele Chs2-V377I has enhanced activity in vitro. We show that Inn1 associates with Chs2 in yeast cell extracts. It also interacts in a yeast two-hybrid assay with the N-terminal 65% of Chs2, which contains the catalytic domain. In addition to compensating for mutations in the Inn1 C2-domain, the dominant CHS2 alleles suppress cytokinesis defects produced by the lack of the Cyk3 protein. Our data support a model in which the C2-domain of Inn1 acts in conjunction with Cyk3 to regulate the catalytic domain of Chs2 during cytokinesis. These findings suggest novel approaches for developing future drugs against important fungal pathogens. © 2012. Published by The Company of Biologists Ltd.