Abstract

Pease et al. introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among n players tolerating up to t faults is (efficiently) possible iff n > 3t. To overcome this severe limitation, Pease et al. introduced a variant of BGP, Authenticated Byzantine General (ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to n > t (which is a huge improvement over the n > 3t). Byzantine faults are the most generic form of faults. In a network not all faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in (t b ,t p )-mixed adversary model where the adversary can corrupt up to any t b players actively and control up to any other t p players passively. We prove that in such a setting, ABG over a completely connected synchronous network of n nodes tolerating a (t b ,t p )-adversary is possible iff n > 2t b +min(t b ,t p ) when t p  > 0. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

Abstract

This paper provides a solution to the issue:“How can we use Wikipedia based concepts in document clustering with lesser human involvement, accompanied by effective improvements in result?” In the devised system, we propose a method to exploit the importance of N-grams in a document and use Wikipedia based additional knowledge for GAAC based document clustering. The importance of N-grams in a document depends on a many features including, but not limited to: frequency, position of their occurrence in a sentence and the position of the sentence in which they occur, in the document. First, we introduce a new similarity measure, which takes the weighted N-gram importance into account, in the calculation of similarity measure while performing document clustering. As a result, the chances of topical similarity in clustering are improved. Second, we use Wikipedia as an additional knowledge base both, to remove noisy entries from the extracted N-grams and to reduce the information gap between N-grams that are conceptually-related, which do not have a match owing to differences in writing scheme or strategies. Our experimental results on the publicly available text dataset clearly show that our devised system has a significant improvement in performance over bag-of-words based state-of-the-art systems in this area.

Abstract

We study the interplay of network connectivity and the issues related to the 'possibility', 'feasibility' and 'optimality' for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.

Abstract

In this paper we, present (1) an unsupervised system for AESOP task and (2) a generic multi-document summarization system for guided summarization task. We propose the use of:(1) the role and importance of words and sentences in document and,(2) number and coverage strength of topics in document for both AESOP and Guided summarization task. We also use some other statistical features, simple heuristics and grammatical facts to capture the important facts and information from source document (s).

Abstract

Reliable message transmission is a fundamental problem in distributed communication networks. Of late, several interesting results have been obtained by modelling the network as a directed graph. An important result among them was due to Bhavani et al. [Unconditionally reliable message transmission in directed networks, 18 in: SODA’08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, USA, 2008, pp. 1048–1055], where it was shown that if a negligible probability of error is allowed, the connectivity required in a synchronous network for unconditionally reliable message transmission (URMT) is significantly reduced. We refer to the variant of URMT studied by them as Monte Carlo URMT; here the receiver is allowed to output an incorrect message with small probability. Another interesting variant which has received little attention so far in the literature is the Las Vegas variant, where the receiver is allowed to abort with a small probability, but never to output an incorrect message. We show that the minimum connectivity requirements for the existence of Las Vegas URMT protocols over synchronous networks are the same as that of Monte Carlo URMT protocols over asynchronous networks—a surprising equivalence between two very different models. Furthermore, we show that the higher connectivity requirements of Las Vegas URMT over asynchronous networks match exactly with that of zero-error (perfect) variant over (a)synchronous networks. We also show that there exists a family of graphs where in the number of critical edges for the ‘easier’ randomized variants are asymptotically higher than that for the perfect variants. Hence, our results demonstrate an interesting interplay between (im)perfectness, synchrony and connectivity for the case of reliable message transmission.

Abstract

We use a combination of database analysis and quantum chemical studies to investigate the role of cis and trans Hoogsteen:Hoogsteen (H:H) base pairs and associated higher-order structures in RNA. We add three new examples to the list of previously identified base-pair combinations belonging to these families and, in addition to contextual classification and characterization of their structural and energetic features, we compare their interbase interaction energies and propensities toward participation in triplets and quartets. We find that some base pairs, which are nonplanar in their isolated minimum energy geometries, attain planarity and stability upon triplet formation. A:A H:H trans is the most frequent H:H combination in RNA structures. This base pair occurs at many distinct positions in known rRNA structures, where it helps in the interaction of ribosomal domains in the 50S subunit. It is also present as a part of tertiary interaction in tRNA structures. Although quantum chemical studies suggest an intrinsically nonplanar geometry for this base pair in isolated form, it has the tendency to attain planar geometry in RNA crystal structures by forming higher-order tertiary interactions or in the presence of additional base–phosphate interactions. The tendency of this base pair to form such additional interactions may be helpful in bringing together different segments of RNA, thus making it suitable for the role of facilitator for RNA folding. This also explains the high occurrence frequency of this base pair among all H:H interactions.

Abstract

Base pairs belonging to the cis Hoogsteen: sugar-edge (H:S) family play important structural roles in folded RNA molecules. Several of these are present in internal loops, where they are involved in interactions leading to planar dinucleotide platforms which stabilize higher order structures such as base triplets and quartets. We report results of analysis of 30 representative examples spanning 16 possible base pair combinations, with several of them showing multimodality of base pairing geometry. The geometries of 23 of these base pairs were modeled directly from coordinates extracted from RNA crystal structures. The other seven were predicted structures which were modeled on the basis of observed isosteric analogues. After appropriate satisfaction of residual valencies, these structures were relaxed using the B3LYP/6-31G(d,p) method and interaction energies were derived at the RIMP2/aug-cc-pVDZ level of theory. The geometries for each of the studied base pairs have been characterized in terms of the number and nature of H-bonds, rmsd values observed on optimization, base pair geometrical parameters, and sugar pucker analysis. In addition to its evaluation, the nature of intermolecular interaction in these complexes was also analyzed using Morokuma decomposition. The gas phase interaction energies range between −5.2 and −20.6 kcal/mol and, in contrast to the H:S trans base pairs, show enhanced relative importance of the electron correlation component, indicative of the greater role of dispersion energy in stabilization of these base pairs. The rich variety of hydrogen bonding pattern, involving the flexible sugar edge, appears to hold the key to several features of structural motifs, such as planarity and propensity to participate in triplets, observed in this family of base pairs. This work explores these aspects by integrating database analysis, and detailed base pairing geometry analysis at the atomistic level, with ab initio computation of interaction energies. The study, involving alternative classification of base pairs and triplets, provides insights into intrinsic properties of these base pairs and their possible structural and functional roles.

Abstract

Cells from animals adhere to and exert mechanical forces on their surroundings. Cells must control these forces for many biological processes, and dysfunction can lead to pathologies. How the actions of molecules within a cell are coordinated to regulate the adhesive interaction with the extracellular matrix remains poorly understood. It has been observed that cytoplasmic proteins that link integrin cell-surface receptors with the actin cytoskeleton flow with varying rates from the leading edge toward the center of a cell. Here, we explore theoretically how measurable subcellular traction stresses depend on the local speed of retrograde actin flow. In the model, forces result from the stretching of molecular complexes in response to the drag from the flow; because these complexes break with extension-dependent kinetics, the flow results in a decrease in their number when sufficiently large. Competition between these

Abstract

Background Plant biologists have long speculated about the mechanisms that guide pollen tubes to ovules. Although there is now evidence that ovules emit a diffusible attractant, little is known about how this attractant mediates interactions between the pollen tube and the ovules. Results We employ a semi-in vitro assay, in which ovules dissected from Arabidopsis thaliana are arranged around a cut style on artificial medium, to elucidate how ovules release the attractant and how pollen tubes respond to it. Analysis of microscopy images of the semi-in vitro system shows that pollen tubes are more attracted to ovules that are incubated on the medium for longer times before pollen tubes emerge from the cut style. The responses of tubes are consistent with their sensing a gradient of an attractant at 100-150 μm, farther than previously reported. Our …

Abstract

Generation of upsampled tomographic images via combination of rotated lattices has been explored in [1]. In this paper, we evaluate the existing method using real phantom data. Up-sampled tomographic images are generated via combination of rotated hexagonal lattices. Sinogram data is filtered and back-projected on two hexagonal lattices which are rotated versions of each other. Samples from these lattices are interpolated to generate an up-sampled image defined on a square lattice. These results are compared with direct up-sampling method and image ISR-2 algorithm described in [10]. Two PET phantoms - NEMA and Hoffman brain phantom are used for purpose of evaluation. The results of the proposed method show considerable improvement over direct up-sampled image in terms of contrast, sharpness and imaging artifact; but when compared with ISR-2 generated image, the difference in image quality is not significant. A key advantage of the proposed method is that only two images are required for generating a high resolution image whereas ISR2 requires k low resolution images for an up-sampling factor of k.