On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Computing complete test graphs for hierarchical systems

Conformance testing focuses on checking whether an implementation. under test (IUT) behaves according to its specification. Typically, testers are interested it? performing targeted tests that exercise certain features of the IUT This intention is formalized as a test purpose. The tester needs a "strategy" to reach the goal specified by the test purpose. Also, for a particular test case, the strategy should tell the tester whether the IUT has passed, failed. or deviated front the test purpose. In [8] Jeron and Morel show how to compute, for a given finite state machine specification and a test purpose automaton, a complete test graph (CTG) which represents all test strategies. In this paper; we consider the case when the specification is a hierarchical state machine and show how to compute a hierarchical CTG which preserves the hierarchical structure of the specification. We also propose an algorithm for an online test oracle which avoids a space overhead associated with the CTG.

Anti-amyloidogenic property of leaf aqueous extract of Caesalpinia crista

Amyloid beta (A beta) is the major etiological factor implicated in Alzheimer's disease (AD). A beta(42) self-assembles to form oligomers and fibrils via multiple aggregation process. The recent studies aimed to decrease A beta levels or prevention of A beta aggregation which are the major targets for therapeutic intervention. Natural products as alternatives for AD drug discovery are a current trend. We evidenced that Caesalpinia crista leaf aqueous extract has anti-amyloidogenic potential. The studies on pharmacological properties of C. crista are very limited. Our study focused on ability of C. crista leaf aqueous extract on the prevention of (i) the formation of oligomers and aggregates from monomers (Phase I: A beta(42) + extract co-incubation); (ii) the formation of fibrils from oligomers (Phase II: extract added after oligomers formation); and (iii) dis-aggregation of pre-formedfibrils (Phase III: aqueous extract added to matured fibrils and incubated for 9 days). The aggregation kinetics was monitored using thioflavin-T assay and transmission electron microscopy (TEM). The results showed that C. crista aqueous extract could able to inhibit the A beta(42) aggregation from monomers and oligomers and also able todis-aggregate the pre-formed fibrils. The study provides an insight on finding new natural products for AD therapeutics. (C) 2010 Elsevier Ireland Ltd. All rights reserved.

Induction of allergen-specific IgE and IgG responses by anti-idiotypic antibodies

In order to explore idiotypic, anti-idiotypic, and anti-anti-idiotypic responses to allergens, BALB/c mice were immunized with affinity- purified human idiotypic antibodies directed against a highly purified shrimp allergen. This resulted in the production of anti-idiotypic antibodies which were quantitated by using rabbit idiotypic antibodies raised against the same purified allergen. The mouse anti-idiotypic antibodies recognized shrimp-specific human idiotypic antibodies of the IgE isotype from 18 of 20 individuals, and IgG antibodies from 14 of 20 shrimp-sensitive patients. Immunization of BALB/c mice with affinity- purified, allergen-specific anti-idiotypic antibodies induced anti- allergen IgE and IgG responses in the absence of the allergen. This paper thus presents evidence that anti-idiotypic antibodies raised against allergen-specific idiotypic antibodies may substitute for the original allergen in the induction of allergen-specific idiotypic antibodies. The demonstration of shared idiotopes on IgG and IgE antibodies in the sera of shrimp-sensitive patients supports the use of allergen-specific anti-idiotypic antibodies as surrogate allergens.

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) over cap (u, v) of the actual distance d( u, v) between u, v is an element of V is said to be of stretch t if and only if delta(u, v) <= (delta) over cap (u, v) <= t . delta(u, v). Computing all-pairs small stretch distances efficiently ( both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24].

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Structural studies of analgesics and their interactions. XII. Structure and interactions of anti-inflammatory fenamates. A concerted crystallographic and theoretical conformational study

A theoretical conformational analysis of fenamates, which are N-arylated derivatives of anthranilic acid or 2-aminonicotinic acid with different substituents on the aryl (phenyl) group, is reported. The analysis of these analgesics, which are believed to act through the inhibition of prostaglandin biosynthesis, was carried out using semi-empirical potential functions. The results and available crystallographic observations have been critically examined in terms of their relevance to drug action. Crystallographic studies of these drugs and their complexes have revealed that the fenamate molecules share a striking invariant feature, namely, the sixmembered ring bearing the carboxyl group is coplanar with the carboxyl group and the bridging imino group,the coplanarity being stabilized by resonance interactions and an internal hydrogen bond between the imino and carboxyl groups. The results of the theoretical analysis provide a conformational rationale for the observed invariant coplanarity. The second sixmembered ring, which provides hydrophobicity in a substantial part of the molecule, has limited conformational flexibility in meclofenamic, mefenamic and flufenamic acids. Comparison of the conformational energy maps of these acids shows that they could all assume the same conformation when bound to the relevant enzyme. The present study provides a structural explanation for the difference in the activity of niflumic acid, which can assume a conformation in which the whole molecule is nearly planar. The main role of the carboxyl group appears to be to provide a site for intermolecular interactions in addition to helping in stabilizing the invariant coplanar feature and providing hydrophilicity at one end of the molecule. The fenamates thus provide a good example of conformation- dependent molecular asymmetry.

Pre-eclampsia : The role of soluble VEGF receptor-1 and related anti-angiogenic factors beyond

Pre-eclampsia is a pregnancy complication that affects about 5% of all pregnancies. It is known to be associated with alterations in angiogenesis -related factors, such as vascular endothelial growth factor (VEGF). An excess of antiangiogenic substances, especially the soluble receptor-1 of VEGF (sVEGFR-1), has been observed in maternal circulation after the onset of the disease, probably reflecting their increased placental production. Smoking reduces circulating concentrations of sVEGFR-1 in non-pregnant women, and in pregnant women it reduces the risk of pre-eclampsia. Soluble VEGFR-1 acts as a natural antagonist of VEGF and placental growth factor (PlGF) in human circulation, holding a promise for potential therapeutic use. In fact, it has been used as a model to generate a fusion protein, VEGF Trap , which has been found effective in anti-angiogenic treatment of certain tumors and ocular diseases. In the present study, we evaluated the potential use of maternal serum sVEGFR-1, Angiopoietin-2 (Ang-2) and endostatin, three central anti-angiogenic markers, in early prediction of subsequent pre-eclampsia. We also studied whether smoking affects circulating sVEGFR-1 concentrations in pregnant women or their first trimester placental secretion and expression in vitro. Last, in order to allow future discussion on the potential therapy based on sVEGFR-1, we determined the biological half-life of endogenous sVEGFR-1 in human circulation, and measured the concomitant changes in free VEGF concentrations. Blood or placental samples were collected from a total of 268 pregnant women between the years 2001 2007 in Helsinki University Central Hospital for the purposes above. The biomarkers were measured using commercially available enzyme-linked immunosorbent assays (ELISA). For the analyses of sVEGFR-1, Ang-2 and endostatin, a total of 3 240 pregnant women in the Helsinki area were admitted to blood sample collection during two routine ultrasoundscreening visits at 13.7 ± 0.5 (mean ± SD) and 19.2 ± 0.6 weeks of gestation. Of them, 49 women later developing pre-eclampsia were included in the study. Their disease was further classified as mild in 29 and severe in 20 patients. Isolated early-onset intrauterine growth retardation (IUGR) was diagnosed in 16 women with otherwise normal medical histories and uncomplicated pregnancies. Fifty-nine women remaining normotensive, non-proteinuric and finally giving birth to normal-weight infants were picked to serve as the control population of the study. Maternal serum concentrations of Ang-2, endostatin and sVEGFR-1, were increased already at 16 20 weeks of pregnancy, about 13 weeks before the clinical manifestation of preeclampsia. In addition, these biomarkers could be used to identify women at risk with a moderate precision. However, larger patient series are needed to determine whether these markers could be applied for clinical use to predict preeclampsia. Intrauterine growth retardation (IUGR), especially if noted at early stages of pregnancy and not secondary to any other pregnancy complication, has been suggested to be a form of preeclampsia compromising only the placental sufficiency and the fetus, but not affecting the maternal endothelium. In fact, IUGR and preeclampsia have been proposed to share a common vascular etiology in which factors regulating early placental angiogenesis are likely to play a central role. Thus, these factors have been suggested to be involved in the pathogenesis of IUGR. However, circulating sVEGFR-1, Ang-2 and endostatin concentrations were unaffected by subsequent IUGR at early second trimester. Furthermore, smoking was not associated with alterations in maternal circulating sVEGFR-1 or its placental production. The elimination of endogenous sVEGFR-1 after pregnancy was calculated from serial samples of eight pregnant women undergoing elective Caesarean section. As typical for proteins in human compartments, the elimination of sVEGFR-1 was biphasic, containing a rapid halflife of 3.4 h and a slow one of 29 h. The decline in sVEGFR-1 concentrations after mid-trimester legal termination of pregnancy was accompanied with a simultaneous increase in the serum levels of free VEGF so that within a few days after pregnancy VEGF dominated in the maternal circulation. Our study provides novel information on the kinetics of endogenous sVEGFR-1, which serves as a potential tool in the development of new strategies against diseases associated with angiogenic imbalance and alterations in VEGF signaling.