Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Bolaamphiphiles as carriers for siRNA delivery: From chemical syntheses to practical applications

In this study we have investigated a new class of cationic lipids - ``bolaamphiphiles'' or ``bolas'' - for their ability to efficiently deliver small interfering RNAs (siRNAs) to cancer cells. The bolas of this study consist of a hydrophobic chain with one or more positively charged head groups at each end. Recently, we reported that micelles of the bolas GLH-19 and GLH-20 (derived from vernonia oil) efficiently deliver siRNAs, while having relatively low toxicities in vitro and in vivo. Our previous studies validated that; bolaamphiphiles can be designed to vary the magnitude of siRNA shielding, its delivery, and its subsequent release. To further understand the structural features of bolas critical for siRNAs delivery, new structurally related bolas (GLH-58 and GLH-60) were designed and synthesized from jojoba oil. Both bolas have similar hydrophobic domains and contain either one, in GLH-58, or two, in GLH-60 positively charged head groups at each end of the hydrophobic core. We have computationally predicted and experimentally validated that GLH-58 formed more stable nano sized micelles than GLH-60 and performed significantly better in comparison to GLH-60 for siRNA delivery. GLH-58/siRNA complexes demonstrated better efficiency in silencing the expression of the GFP gene in human breast cancer cells at concentrations of 5 mu g/mL, well below the toxic dose. Moreover, delivery of multiple different siRNAs targeting the HIV genome demonstrated further inhibition of virus production. Published by Elsevier B.V.