An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

IN-VITRO CYTOTOXICITY AND CELL CYCLE ANALYSIS OF TWO NOVEL BIS-1, 2, 4-TRIAZOLE DERIVATIVES: 1,4-BIS[5-(5-MERCAPTO-1,3,4-OXADIAZOL-2-yl-METHYL)-THIO-4-(p-TOLYL)-1, 2,4-TRIAZOL-3-yl]-BUTANE (MNP-14) AND 1,4-BIS[5-(CARBETHOXY-METHYL)-THIO-4-(p-ETHOXY PHENYL)-1,2,4-TRIAZOL-3-yl]-BUTANE (MNP-16)

In the present study, we have tested the cytotoxic and DNA damage activity of two novel bis-1,2,4 triazole derivatives, namely 1,4-bis[5-(5-mercapto-1,3,4-oxadiazol-2-yl-methyl)-thio4-(p-tolyl)-1,2 ,4-triazol-3-yl]-butane (MNP-14) and 1,4-bis[5-(carbethoxy-methyl)-thio-4-(p-ethoxy phenyl) -1,2,4-triazol-3-yl]-butane (MNP-16). The effect of these molecules on cellular apoptosis was also determined. The in-vitro cytotoxicity was evaluated by a 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyl tetrazolium bromide (MTT) assay as well as Trypan blue dye exclusion methods against human acute lymphoblastic leukemia (MOLT4) and lung cancer cells (A549). Our results showed that MNP-16 induced significant cytotoxicity (IC50 of 3-5 mu M) compared with MNP-14. The cytotoxicity induced by MNP-16 was time and concentration dependent. The cell cycle analysis by flow cytometry (fluorescence-activated cell sorting [FACS]) revealed that though there was a significant increase in the apoptotic population (sub-G1 phase) with an increased concentration of MNP-14 and 16, there was no cell cycle arrest. Further, the comet assay results indicated considerable DNA

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Albedo enhancement over land to counteract global warming: impacts on hydrological cycle

A recent modelling study has shown that precipitation and runoff over land would increase when the reflectivity of marine clouds is increased to counter global warming. This implies that large scale albedo enhancement over land could lead to a decrease in runoff over land. In this study, we perform simulations using NCAR CAM3.1 that have implications for Solar Radiation Management geoengineering schemes that increase the albedo over land. We find that an increase in reflectivity over land that mitigates the global mean warming from a doubling of CO2 leads to a large residual warming in the southern hemisphere and cooling in the northern hemisphere since most of the land is located in northern hemisphere. Precipitation and runoff over land decrease by 13.4 and 22.3%, respectively, because of a large residual sinking motion over land triggered by albedo enhancement over land. Soil water content also declines when albedo over land is enhanced. The simulated magnitude of hydrological changes over land are much larger when compared to changes over oceans in the recent marine cloud albedo enhancement study since the radiative forcing over land needed (-8.2 W m(-2)) to counter global mean radiative forcing from a doubling of CO2 (3.3 W m(-2)) is approximately twice the forcing needed over the oceans (-4.2 W m(-2)). Our results imply that albedo enhancement over oceans produce climates closer to the unperturbed climate state than do albedo changes on land when the consequences on land hydrology are considered. Our study also has important implications for any intentional or unintentional large scale changes in land surface albedo such as deforestation/afforestation/reforestation, air pollution, and desert and urban albedo modification.

Is meridional circulation important in modelling irregularities of the solar cycle?

We explore the importance of meridional circulation variations in modelling the irregularities of the solar cycle by using the flux transport dynamo model. We show that a fluctuating meridional circulation can reproduce some features of the solar cycle like the Waldmeier effect and the grand minimum. However, we get all these results only if the value of the turbulent diffusivity in the convection zone is reasonably high.

Context dependent splicing functions of Bud31/Ycr063w define its role in budding and cell cycle progression

The yeast Bud31 protein, a Prp19 complex (NTC) member, aids spliceosome assembly and thus promotes efficient pre-mRNA splicing. The bud31 null cells show mild budding abnormalities at optimal growth temperatures and, at higher temperatures, have growth defects with aberrant budding. Here we have assessed cell cycle transitions which require Bud31. We find Bud31 facilitates passage through G1-S regulatory point (Start) but is not needed for G2-M transition or for exit from mitosis. To co-relate Bud31 functions in cell division with splicing, we studied the splicing status of transcripts that encode proteins involved in budding. We find Bud31 promotes efficient splicing of only some of these pre-mRNAs, for example, ARP2 and SRC1. Wild type cells have a long and a short isoform of SRC1 mRNA and protein, out of which the shorter mRNA splice variant is predominant. bud31 Delta cells show inefficient SRC1 splicing and entirely lack the shorter SRC1 spliced mRNA isoform. Yeast PRP17, another NTC sub-complex member, is also required for G1-S and G2-M cell cycle transitions. We examined genetic interactions between BUD31 and PRP17. While both factors were needed for efficient cell cycle dependent gene expression, our data indicate that distinct pre-mRNAs depend on each of these non-essential splicing factors.