Grøstl - a SHA-3 candidate

Grøstl is a SHA-3 candidate proposal. Grøstl is an iterated hash function with a compression function built from two �fixed, large, distinct permutations. The design of Grøstl is transparent and based on principles very different from those used in the SHA-family. The two permutations are constructed using the wide trail design strategy, which makes it possible to give strong statements about the resistance of Grøstl against large classes of cryptanalytic attacks. Moreover, if these permutations are assumed to be ideal, there is a proof for the security of the hash function. Grøstl is a byte-oriented SP-network which borrows components from the AES. The S-box used is identical to the one used in the block cipher AES and the diffusion layers are constructed in a similar manner to those of the AES. As a consequence there is a very strong confusion and diffusion in Grøstl

Discovery of genes that affect human brain connectivity: A genome-wide analysis of the connectome

Human brain connectivity is disrupted in a wide range of disorders from Alzheimer's disease to autism but little is known about which specific genes affect it. Here we conducted a genome-wide association for connectivity matrices that capture information on the density of fiber connections between 70 brain regions. We scanned a large twin cohort (N=366) with 4-Tesla high angular resolution diffusion imaging (105-gradient HARDI). Using whole brain HARDI tractography, we extracted a relatively sparse 70×70 matrix representing fiber density between all pairs of cortical regions automatically labeled in co-registered anatomical scans. Additive genetic factors accounted for 1-58% of the variance in connectivity between 90 (of 122) tested nodes. We discovered genome-wide significant associations between variants and connectivity. GWAS permutations at various levels of heritability, and split-sample replication, validated our genetic findings. The resulting genes may offer new leads for mechanisms influencing aberrant connectivity and neurodegeneration. © 2012 IEEE.

An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Distinct Disulfide Isomers of mu-Conotoxins KIIIA and KIIIB Block Voltage-Gated Sodium Channels

In the preparation of synthetic conotoxins containing multiple disulfide bonds, oxidative folding can produce numerous permutations of disulfide bond connectivities. Establishing the native disulfide connectivities thus presents a significant challenge when the venom-derived peptide is not available, as is increasingly the case when conotoxins are identified from cDNA sequences. Here, we investigate the disulfide connectivity of mu-conotoxin KIIIA, which was predicted originally to have a C1-C9,C2-C15,C4-C16] disulfide pattern based on homology with closely related mu-conotoxins. The two major isomers of synthetic mu-KIIIA formed during oxidative folding were purified and their disulfide connectivities mapped by direct mass spectrometric collision-induced dissociation fragmentation of the disulfide-bonded polypeptides. Our results show that the major oxidative folding product adopts a C1-C15,C2-C9,C4-C16] disulfide connectivity, while the minor product adopts a C1-C16,C2-C9,C4-C15] connectivity. Both of these peptides were potent blockers of Na(v)1.2 (K-d values of 5 and 230 nM, respectively). The solution structure for mu-KIIIA based on nuclear magnetic resonance data was recalculated with the C1-C15,C2-C9,C4-C16] disulfide pattern; its structure was very similar to the mu-KIIIA structure calculated with the incorrect C1-C9,C2-C15,C4-C16] disulfide pattern, with an alpha-helix spanning residues 7-12. In addition, the major folding isomers of mu-KIIIB, an N-terminally extended isoform of mu-KIIIA, identified from its cDNA sequence, were isolated. These folding products had the same disulfide connectivities as mu-KIIIA, and both blocked Na(v)1.2 (K-d values of 470 and 26 nM, respectively). Our results establish that the preferred disulfide pattern of synthetic mu-KIIIA and mu-KIIIB folded in vitro is 1-5/2-4/3-6 but that other disulfide isomers are also potent sodium channel blockers. These findings raise questions about the disulfide pattern(s) of mu-KIIIA in the venom of Conus kinoshitai; indeed, the presence of multiple disulfide isomers in the venom could provide a means of further expanding the snail's repertoire of active peptides.

CLAP: A web-server for automatic classification of proteins with special reference to multi-domain proteins

Background: The function of a protein can be deciphered with higher accuracy from its structure than from its amino acid sequence. Due to the huge gap in the available protein sequence and structural space, tools that can generate functionally homogeneous clusters using only the sequence information, hold great importance. For this, traditional alignment-based tools work well in most cases and clustering is performed on the basis of sequence similarity. But, in the case of multi-domain proteins, the alignment quality might be poor due to varied lengths of the proteins, domain shuffling or circular permutations. Multi-domain proteins are ubiquitous in nature, hence alignment-free tools, which overcome the shortcomings of alignment-based protein comparison methods, are required. Further, existing tools classify proteins using only domain-level information and hence miss out on the information encoded in the tethered regions or accessory domains. Our method, on the other hand, takes into account the full-length sequence of a protein, consolidating the complete sequence information to understand a given protein better. Results: Our web-server, CLAP (Classification of Proteins), is one such alignment-free software for automatic classification of protein sequences. It utilizes a pattern-matching algorithm that assigns local matching scores (LMS) to residues that are a part of the matched patterns between two sequences being compared. CLAP works on full-length sequences and does not require prior domain definitions. Pilot studies undertaken previously on protein kinases and immunoglobulins have shown that CLAP yields clusters, which have high functional and domain architectural similarity. Moreover, parsing at a statistically determined cut-off resulted in clusters that corroborated with the sub-family level classification of that particular domain family. Conclusions: CLAP is a useful protein-clustering tool, independent of domain assignment, domain order, sequence length and domain diversity. Our method can be used for any set of protein sequences, yielding functionally relevant clusters with high domain architectural homogeneity. The CLAP web server is freely available for academic use at http://nslab.mbu.iisc.ernet.in/clap/.

Genome-wide analysis correlates Ayurveda Prakriti

The practice of Ayurveda, the traditional medicine of India, is based on the concept of three major constitutional types (Vata, Pitta and Kapha) defined as ``Prakriti''. To the best of our knowledge, no study has convincingly correlated genomic variations with the classification of Prakriti. In the present study, we performed genome-wide SNP (single nucleotide polymorphism) analysis (Affymetrix, 6.0) of 262 well-classified male individuals (after screening 3416 subjects) belonging to three Prakritis. We found 52 SNPs (p <= 1 x 10(-5)) were significantly different between Prakritis, without any confounding effect of stratification, after 10(6) permutations. Principal component analysis (PCA) of these SNPs classified 262 individuals into their respective groups (Vata, Pitta and Kapha) irrespective of their ancestry, which represent its power in categorization. We further validated our finding with 297 Indian population samples with known ancestry. Subsequently, we found that PGM1 correlates with phenotype of Pitta as described in the ancient text of Caraka Samhita, suggesting that the phenotypic classification of India's traditional medicine has a genetic basis; and its Prakriti-based practice in vogue for many centuries resonates with personalized medicine.

Sampling and learning the Mallows and Generalized Mallows models under the Cayley distance

[EN]The Mallows and Generalized Mallows models are compact yet powerful and natural ways of representing a probability distribution over the space of permutations. In this paper we deal with the problems of sampling and learning (estimating) such distributions when the metric on permutations is the Cayley distance. We propose new methods for both operations, whose performance is shown through several experiments. We also introduce novel procedures to count and randomly generate permutations at a given Cayley distance both with and without certain structural restrictions. An application in the field of biology is given to motivate the interest of this model.

Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance

[EN]In this paper we deal with distributions over permutation spaces. The Mallows model is the mode l in use. The associated distance for permutations is the Hamming distance.

Sampling and learning the Mallows model under the Ulam distance

[EN]In this paper we deal with probability distributions over permutation spaces. The Probability model in use is the Mallows model. The distance for permutations that the model uses in the Ulam distance.

Extending Distance-based Ranking Models In Estimation of Distribution Algorithms

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall’s-t distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

Rewriting Schemes for Flash Memory

Flash memory is a leading storage media with excellent features such as random access and high storage density. However, it also faces significant reliability and endurance challenges. In flash memory, the charge level in the cells can be easily increased, but removing charge requires an expensive erasure operation. In this thesis we study rewriting schemes that enable the data stored in a set of cells to be rewritten by only increasing the charge level in the cells. We consider two types of modulation scheme; a convectional modulation based on the absolute levels of the cells, and a recently-proposed scheme based on the relative cell levels, called rank modulation. The contributions of this thesis to the study of rewriting schemes for rank modulation include the following: we

•propose a new method of rewriting in rank modulation, beyond the previously proposed method of “push-to-the-top”;

•study the limits of rewriting with the newly proposed method, and derive a tight upper bound of 1 bit per cell;

•extend the rank-modulation scheme to support rankings with repetitions, in order to improve the storage density;

•derive a tight upper bound of 2 bits per cell for rewriting in rank modulation with repetitions;

•construct an efficient rewriting scheme that asymptotically approaches the upper bound of 2 bit per cell.

The next part of this thesis studies rewriting schemes for a conventional absolute-levels modulation. The considered model is called “write-once memory” (WOM). We focus on WOM schemes that achieve the capacity of the model. In recent years several capacity-achieving WOM schemes were proposed, based on polar codes and randomness extractors. The contributions of this thesis to the study of WOM scheme include the following: we

•propose a new capacity-achievingWOM scheme based on sparse-graph codes, and show its attractive properties for practical implementation;

•improve the design of polarWOMschemes to remove the reliance on shared randomness and include an error-correction capability.

The last part of the thesis studies the local rank-modulation (LRM) scheme, in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. The LRM scheme is used to simulate a single conventional multi-level flash cell. The simulated cell is realized by a Gray code traversing all the relative-value states where, physically, the transition between two adjacent states in the Gray code is achieved by using a single “push-to-the-top” operation. The main results of the last part of the thesis are two constructions of Gray codes with asymptotically-optimal rate.

Imidazolium-Based Organic Structure Directing Agents for the Synthesis of Microporous Materials

The central theme of this thesis is the use of imidazolium-based organic structure directing agents (OSDAs) in microporous materials synthesis. Imidazoliums are advantageous OSDAs as they are relatively inexpensive and simple to prepare, show robust stability under microporous material synthesis conditions, have led to a wide range of products, and have many permutations in structure that can be explored. The work I present involves the use of mono-, di-, and triquaternary imidazolium-based OSDAs in a wide variety of microporous material syntheses. Much of this work was motivated by successful computational predictions (Chapter 2) that led me to continue to explore these types of OSDAs. Some of the important discoveries with these OSDAs include the following: 1) Experimental evaluation and confirmation of a computational method that predicted a new OSDA for pure-silica STW, a desired framework containing helical pores that was previously very difficult to synthesize. 2) Discovery of a number of new imidazolium OSDAs to synthesize zeolite RTH, a zeolite desired for both the methanol-to-olefins reaction as well as NOX reduction in exhaust gases. This discovery enables the use of RTH for many additional investigations as the previous OSDA used to make this framework was difficult to synthesize, such that no large scale preparations would be practical. 3) The synthesis of pure-silica RTH by topotactic condensation from a layered precursor (denoted CIT-10), that can also be pillared to make a new framework material with an expanded pore system, denoted CIT-11, that can be calcined to form a new microporous material, denoted CIT-12. CIT-10 is also interesting since it is the first layered material to contain 8 membered rings through the layers, making it potentially useful in separations if delamination methods can be developed. 4) The synthesis of a new microporous material, denoted CIT-7 (framework code CSV) that contains a 2-dimensional system of 8 and 10 membered rings with a large cage at channel intersections. This material is especially important since it can be synthesized as a pure-silica framework under low-water, fluoride-mediated synthesis conditions, and as an aluminosilicate material under hydroxide mediated conditions. 5) The synthesis of high-silica heulandite (HEU) by topotactic condensation as well as direct synthesis, demonstrating new, more hydrothermally stable compositions of a previously known framework. 6) The synthesis of germanosilicate and aluminophosphate LTA using a triquaternary OSDA. All of these materials show the diverse range of products that can be formed from OSDAs that can be prepared by straightforward syntheses and have made many of these materials accessible for the first time under facile zeolite synthesis conditions.

Two topics in elementary particle physics. I. Crossing as a group and elimination of exotic channels. II. Real parts of meson-nucleon forward scattering amplitudes.

I. Crossing transformations constitute a group of permutations under which the scattering amplitude is invariant. Using Mandelstem's analyticity, we decompose the amplitude into irreducible representations of this group. The usual quantum numbers, such as isospin or SU(3), are "crossing-invariant". Thus no higher symmetry is generated by crossing itself. However, elimination of certain quantum numbers in intermediate states is not crossing-invariant, and higher symmetries have to be introduced to make it possible. The current literature on exchange degeneracy is a manifestation of this statement. To exemplify application of our analysis, we show how, starting with SU(3) invariance, one can use crossing and the absence of exotic channels to derive the quark-model picture of the tensor nonet. No detailed dynamical input is used.

II. A dispersion relation calculation of the real parts of forward π^±p and K^±p scattering amplitudes is carried out under the assumption of constant total cross sections in the Serpukhov energy range. Comparison with existing experimental results as well as predictions for future high energy experiments are presented and discussed. Electromagnetic effects are found to be too small to account for the expected difference between the π^-p and π⁺p total cross sections at higher energies.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).