Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Cluster labeling for multilingual scatter/gather using comparable corpora

Scatter/Gather systems are increasingly becoming useful in browsing document corpora. Usability of the present-day systems are restricted to monolingual corpora, and their methods for clustering and labeling do not easily extend to the multilingual setting, especially in the absence of dictionaries/machine translation. In this paper, we study the cluster labeling problem for multilingual corpora in the absence of machine translation, but using comparable corpora. Using a variational approach, we show that multilingual topic models can effectively handle the cluster labeling problem, which in turn allows us to design a novel Scatter/Gather system ShoBha. Experimental results on three datasets, namely the Canadian Hansards corpus, the entire overlapping Wikipedia of English, Hindi and Bengali articles, and a trilingual news corpus containing 41,000 articles, confirm the utility of the proposed system.

Studies of grand minima in sunspot cycles by using a flux transport solar dynamo model

We propose that grand minima in solar activity are caused by simultaneous fluctuations in the meridional circulation and the Babcock-Leighton mechanism for the poloidal field generation in the flux transport dynamo model. We present the following results: (a) fluctuations in the meridional circulation are more effective in producing grand minima; (b) both sudden and gradual initiations of grand minima are possible; (c) distributions of durations and waiting times between grand minima seem to be exponential; (d) the coherence time of the meridional circulation has an effect on the number and the average duration of grand minima, with a coherence time of about 30 yr being consistent with observational data. We also study the occurrence of grand maxima and find that the distributions of durations and waiting times between grand maxima are also exponential, like the grand minima. Finally we address the question of whether the Babcock-Leighton mechanism can be operative during grand minima when there are no sunspots. We show that an alpha-effect restricted to the upper portions of the convection zone can pull the dynamo out of the grand minima and can match various observational requirements if the amplitude of this alpha-effect is suitably fine-tuned.

Energy Hyperspace for Stacking Interaction in AU/AU Dinucleotide Step: Dispersion-Corrected Density Functional Theory Study

Double helical structures of DNA and RNA are mostly determined by base pair stacking interactions, which give them the base sequence-directed features, such as small roll values for the purine-pyrimidine steps. Earlier attempts to characterize stacking interactions were mostly restricted to calculations on fiber diffraction geometries or optimized structure using ab initio calculations lacking variation in geometry to comment on rather unusual large roll values observed in AU/AU base pair step in crystal structures of RNA double helices. We have generated stacking energy hyperspace by modeling geometries with variations along the important degrees of freedom, roll, and slide, which were chosen via statistical analysis as maximally sequence dependent. Corresponding energy contours were constructed by several quantum chemical methods including dispersion corrections. This analysis established the most suitable methods for stacked base pair systems despite the limitation imparted by number of atom in a base pair step to employ very high level of theory. All the methods predict negative roll value and near-zero slide to be most favorable for the purine-pyrimidine steps, in agreement with Calladine's steric clash based rule. Successive base pairs in RNA are always linked by sugar-phosphate backbone with C3-endo sugars and this demands C1-C1 distance of about 5.4 angstrom along the chains. Consideration of an energy penalty term for deviation of C1-C1 distance from the mean value, to the recent DFT-D functionals, specifically B97X-D appears to predict reliable energy contour for AU/AU step. Such distance-based penalty improves energy contours for the other purine-pyrimidine sequences also. (c) 2013 Wiley Periodicals, Inc. Biopolymers 101: 107-120, 2014.

Moving to stay in place: behavioral mechanisms for coexistence of African large carnivores

Most ecosystems have multiple predator species that not only compete for shared prey, but also pose direct threats to each other. These intraguild interactions are key drivers of carnivore community structure, with ecosystem-wide cascading effects. Yet, behavioral mechanisms for coexistence of multiple carnivore species remain poorly understood. The challenges of studying large, free-ranging carnivores have resulted in mainly coarse-scale examination of behavioral strategies without information about all interacting competitors. We overcame some of these challenges by examining the concurrent fine-scale movement decisions of almost all individuals of four large mammalian carnivore species in a closed terrestrial system. We found that the intensity of intraguild interactions did not follow a simple hierarchical allometric pattern, because spatial and behavioral tactics of subordinate species changed with threat and resource levels across seasons. Lions (Panthera leo) were generally unrestricted and anchored themselves in areas rich in not only their principal prey, but also, during periods of resource limitation (dry season), rich in the main prey for other carnivores. Because of this, the greatest cost (potential intraguild predation) for subordinate carnivores was spatially coupled with the highest potential benefit of resource acquisition (prey-rich areas), especially in the dry season. Leopard (P. pardus) and cheetah (Acinonyx jubatus) overlapped with the home range of lions but minimized their risk using fine-scaled avoidance behaviors and restricted resource acquisition tactics. The cost of intraguild competition was most apparent for cheetahs, especially during the wet season, as areas with energetically rewarding large prey (wildebeest) were avoided when they overlapped highly with the activity areas of lions. Contrary to expectation, the smallest species (African wild dog, Lycaon pictus) did not avoid only lions, but also used multiple tactics to minimize encountering all other competitors. Intraguild competition thus forced wild dogs into areas with the lowest resource availability year round. Coexistence of multiple carnivore species has typically been explained by dietary niche separation, but our multi-scaled movement results suggest that differences in resource acquisition may instead be a consequence of avoiding intraguild competition. We generate a more realistic representation of hierarchical behavioral interactions that may ultimately drive spatially explicit trophic structures of multi-predator communities.

Type IA topoisomerase inhibition by clamp closure

Bacterial DNA topoisomerase I (topoI) catalyzes relaxation of negatively supercoiled DNA. The enzyme alters DNA topology through protein-operated DNA gate, switching between open and closed conformations during its reaction. We describe the mechanism of inhibition of Mycobacterium smegmatis and Mycobacterium tuberculosis topoI by monoclonal antibodies (mAbs) that bind with high affinity and inhibit at 10-50 nM concentration. Unlike other inhibitors of topoisomerases, the mAbs inhibited several steps of relaxation reaction, namely DNA binding, cleavage, strand passage, and enzyme-DNA dissociation. The enhanced religation of the cleaved DNA in presence of the mAb indicated closing of the enzyme DNA gate. The formation of enzyme-DNA heterocatenane in the presence of the mAbs as a result of closing the gate could be inferred by the salt resistance of the complex, visualized by atomic force microscopy and confirmed by fluorescence measurements. Locking the enzyme-DNA complex as a closed clamp restricted the movements of the DNA gate, affecting all of the major steps of the relaxation reaction. Enzyme trapped on DNA in closed clamp conformation formed roadblock for the elongating DNA polymerase. The unusual multistep inhibition of mycobacterial topoisomerases may facilitate lead molecule development, and the mAbs would also serve as valuable tools to probe the enzyme mechanism.

Scalable sequential alternating proximal methods for sparse structural SVMs and CRFs

Structural Support Vector Machines (SSVMs) and Conditional Random Fields (CRFs) are popular discriminative methods used for classifying structured and complex objects like parse trees, image segments and part-of-speech tags. The datasets involved are very large dimensional, and the models designed using typical training algorithms for SSVMs and CRFs are non-sparse. This non-sparse nature of models results in slow inference. Thus, there is a need to devise new algorithms for sparse SSVM and CRF classifier design. Use of elastic net and L1-regularizer has already been explored for solving primal CRF and SSVM problems, respectively, to design sparse classifiers. In this work, we focus on dual elastic net regularized SSVM and CRF. By exploiting the weakly coupled structure of these convex programming problems, we propose a new sequential alternating proximal (SAP) algorithm to solve these dual problems. This algorithm works by sequentially visiting each training set example and solving a simple subproblem restricted to a small subset of variables associated with that example. Numerical experiments on various benchmark sequence labeling datasets demonstrate that the proposed algorithm scales well. Further, the classifiers designed are sparser than those designed by solving the respective primal problems and demonstrate comparable generalization performance. Thus, the proposed SAP algorithm is a useful alternative for sparse SSVM and CRF classifier design.

Pure shift NMR approach for fast and accurate extraction of heteronuclear couplings

The direct and accurate determination of heteronuclear ((n)J(HX), X = F-19, P-31) couplings from the one dimensional H-1-NMR spectrum is severely hampered due to the simultaneous presence of large numbers of (n)J(HH). The present study demonstrates the utility of the pure shift NMR approach for spectral simplification, and precise and direct measurement of heteronuclear couplings. As a consequence of refocusing of homonuclear couplings ((n)J(HH)) by the pure shift NMR, only heteronuclear couplings ((n)J(HX)) appear as simple multiplets at the resonance position of each chemically non-equivalent proton, enabling their direct measurement from the 1D-H-1 spectrum. The experiment is demonstrated on a number of molecules containing either F-19 or P-31, where (n)J(HF) and (n)J(HP) could be precisely measured in a straightforward manner. The distinct advantage of the experiment is demonstrated on molecules containing more than one fluorine atom, where most of the available NMR experiments fail or have restricted utility.

Freeform Skeletal Shape Optimization of Compliant Mechanisms

Compliant mechanisms are elastic continua used to transmit or transform force and motion mechanically. The topology optimization methods developed for compliant mechanisms also give the shape for a chosen parameterization of the design domain with a fixed mesh. However, in these methods, the shapes of the flexible segments in the resulting optimal solutions are restricted either by the type or the resolution of the design parameterization. This limitation is overcome in this paper by focusing on optimizing the skeletal shape of the compliant segments in a given topology. It is accomplished by identifying such segments in the topology and representing them using Bezier curves. The vertices of the Bezier control polygon are used to parameterize the shape-design space. Uniform parameter steps of the Bezier curves naturally enable adaptive finite element discretization of the segments as their shapes change. Practical constraints such as avoiding intersections with other segments, self-intersections, and restrictions on the available space and material, are incorporated into the formulation. A multi-criteria function from our prior work is used as the objective. Analytical sensitivity analysis for the objective and constraints is presented and is used in the numerical optimization. Examples are included to illustrate the shape optimization method.

INDUCTION OF FOLDED STRUCTURES IN DESIGNED PEPTIDES USING CONFORMATIONALLY CONSTRAINED RESIDUES

Folding into compact globular structures, with well-defined modules of secondary structure, appears to be a characteristic of long polypeptide chains, with a specific patterning of coded amino acid residues along the length of sequence. Cooperative hydrogen bond driven secondary structure formation and solvent forces, which contribute favorably to the entropy of folding, by promoting compaction of the polymeric chain, have long been discussed as major determinants of the folding process. First principles design approaches, which use non-coded amino acids, employ an alternative structure directing strategy, by using amino acid residues which exhibit a strong conformational bias for specific regions of the Ramachandran map. This overview of ongoing studies in the authors' laboratory, attempts to explore the use of conformationally restricted amino acid residues in the design of peptides with well-defined secondary structures. Short peptides composed of 20 genetically coded amino acids usually exist in solution as an ensemble of equilibrating conformations. Apolar peptide sequences, which are readily soluble in organic solvents like chloroform and methanol, facilitate formation of structures which are predominately driven by intramolecular hydrogen bond formation. The choice of sequences containing residues with a limited range of conformational choices strongly favors formation of local turn structures, stabilized by short range intramolecular hydrogen bonds. Two residue beta-turns can nucleate either helical or hairpin folding, depending on the precise conformation of the turn segment Restriction of the conformational space available to amino acid residues is easily achieved by introduction of an additional alkyl group at the C alpha carbon atom or by side chain backbone cyclization, as in proline. Studies of synthetic sequences incorporating two prototype residues alpha-aminoisobutyric acid (Aib) and D-proline (DPro) illustrate the utility of the strategy in construction of helices and hairpins. Extensions to the design of conformationally switchable sequences and structurally defined hybrid peptides containing backbone homologated residues are also surveyed.

Socio-cultural protection of endemic trees in humanised landscape

Culturally protected forest patches or sacred groves have been the integral part of many traditional societies. This age old tradition is a classic instance of community driven nature conservation sheltering native biodiversity and supporting various ecosystem functions particularly hydrology. The current work in Central Western Ghats of Karnataka, India, highlights that even small sacred groves amidst humanised landscapes serve as tiny islands of biodiversity, especially of rare and endemic species. Temporal analysis of landuse dynamics reveals the changing pattern of the studied landscape. There is fast reduction of forest cover (15.14-11.02 %) in last 20 years to meet up the demand of agricultural land and plantation programs. A thorough survey and assessment of woody endemic species distribution in the 25 km(2) study area documented presence of 19 endemic species. The distribution of these species is highly skewed towards the culturally protected patches in comparison to other land use elements. It is found that, among the 19 woody endemic species, those with greater ecological amplitude are widely distributed in the studied landscape in groves as well as other land use forms whereas, natural population of the sensitive endemics are very much restricted in the sacred grove fragments. The recent degradation in the sacred grove system is perhaps, due to weakening of traditional belief systems and associated laxity in grove protection leading to biotic disturbances. Revitalisation of traditional practices related to conservation of sacred groves can go a long way in strengthening natural ecological systems of fragile humid tropical landscape.

Design Aspects of Luminescent Organic Crystals

With the progress of modern material science and successful commercialisations of organic-electronics, the field of organic luminescent materials has gained much attention in recent years. For a long time, the concepts and knowledge of photoluminescence (i.e. fluorescence and phosphorescence) were restricted to the solution phase as the exceptions of fluorescence quenching in condensed state were yet to be discovered. However, in the last few decades, researchers around the globe have come up with a number of promising strategies and concepts to systematically design solid-state emissive organic materials. In particular, the manipulations of ordered solid state structures and intermolecular strong and weak interactions provide a basis for understanding structure-property relationship and serve as an important tool for the design of newer, better and more efficient luminescent materials. In this short review, recent developments in this field will be presented.

Thermoelectric properties of indium doped PbTe1-ySey alloys

Lead telluride and its alloys are well known for their thermoelectric applications. Here, a systematic study of PbTe1-ySey alloys doped with indium has been done. The powder X-Ray diffraction combined with Rietveld analysis confirmed the polycrystalline single phase nature of the samples, while microstructural analysis with scanning electron microscope results showed densification of samples and presence of micrometer sized particles. The temperature dependent transport properties showed that in these alloys, indium neither pinned the Fermi level as it does in PbTe, nor acted as a resonant dopant as in SnTe. At high temperatures, bipolar effect was observed which restricted the zT to 0.66 at 800 K for the sample with 30% Se content. (C) 2014 AIP Publishing LLC.

Nutritional benefits from domatia inhabitants in an ant-plant interaction: interlopers do pay the rent

1. How a symbiosis originates and is maintained are important evolutionary questions. Symbioses in myrmecophytes (plants providing nesting for ants) are believed to be maintained by protection and nutrients provided by specialist plant-ants in exchange for nesting spaces (called domatia) and nourishment offered by ant-plants. However, besides the benefits accrued from housing protective ants, the mechanisms contributing to the fitness advantages of bearing domatia have rarely been examined, especially because the domatia trait is usually constitutively expressed, and many myrmecophytes have obligate mutualisms with single ant species resulting in invariant conditions. 2. In the unspecialized ant-plant Humboldtia brunonis (Fabaceae) that offers extrafloral nectar to ants, only some plants produce domatia in the form of hollow internodes. These domatia have a self-opening slit making them more prone to interlopers and are occupied mostly by non-protective ants and other invertebrates, especially arboreal earthworms. The protection mutualism with ants is restricted in geographical extent, occurring only at a few sites in the southernmost part of this plant's range in the Western Ghats of India. 3. We examined nutrient flux from domatia residents to the plant using stable isotopes. We found that between 9% (earthworms) and 17% (protective or non-protective ants) of nitrogen of plant tissues nearest the domatium came from domatia inhabitants. Therefore, interlopers such as earthworms and non-protective ants contributed positively to the nitrogen budget of localized plant modules of this understorey tree. N-15-enriched feeding experiments with protective ants demonstrated that nutrients flowed from domatia inhabitants to nearby plant modules. Fruit set did not differ between paired hand-pollinated inflorescences on domatia and non-domatia bearing branches. This was possibly due to the nutrient flux from domatia to adjacent branches without domatia within localized modules. 4. This study has demonstrated the nutritive role of non-protective ants and non-ant invertebrates, hitherto referred to as interlopers, in an unspecialized myrmecophyte. Our study suggests that even before the establishment of a specialized ant-plant protection mutualism, nutritional benefits conferred by domatia inhabitants can explain the fitness benefits of bearing domatia, and thus the maintenance of a trait that facilitates the establishment of a specialized ant-plant symbiosis.

Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually ``not too far apart'', without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm STACS, 2013]. That is, there is no algorithm solving the problem in time 2 degrees((k))n(O(1)). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time O(2(O(root dk)) + m + n). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2 degrees((k))n(O(1)). We show, further, that even the problem of deleting edges to obtain a graph with d s-clubs cannot be solved in time 2 degrees((k))n(O)(1) for any fixed s, d >= 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.