Filling-in Void and Sparse Regions in Protein Sequence Space by Protein-Like Artificial Sequences Enables Remarkable Enhancement in Remote Homology Detection Capability

Protein functional annotation relies on the identification of accurate relationships, sequence divergence being a key factor. This is especially evident when distant protein relationships are demonstrated only with three-dimensional structures. To address this challenge, we describe a computational approach to purposefully bridge gaps between related protein families through directed design of protein-like ``linker'' sequences. For this, we represented SCOP domain families, integrated with sequence homologues, as multiple profiles and performed HMM-HMM alignments between related domain families. Where convincing alignments were achieved, we applied a roulette wheel-based method to design 3,611,010 protein-like sequences corresponding to 374 SCOP folds. To analyze their ability to link proteins in homology searches, we used 3024 queries to search two databases, one containing only natural sequences and another one additionally containing designed sequences. Our results showed that augmented database searches showed up to 30% improvement in fold coverage for over 74% of the folds, with 52 folds achieving all theoretically possible connections. Although sequences could not be designed between some families, the availability of designed sequences between other families within the fold established the sequence continuum to demonstrate 373 difficult relationships. Ultimately, as a practical and realistic extension, we demonstrate that such protein-like sequences can be ``plugged-into'' routine and generic sequence database searches to empower not only remote homology detection but also fold recognition. Our richly statistically supported findings show that complementary searches in both databases will increase the effectiveness of sequence-based searches in recognizing all homologues sharing a common fold. (C) 2013 Elsevier Ltd. All rights reserved.

Analytical Closed-Form Expressions for Harmonic Distortion Corresponding to Novel Switching Sequences for Neutral-Point-Clamped Inverters

Analytical closed-form expressions for harmonic distortion factors corresponding to various pulsewidth modulation (PWM) techniques for a two-level inverter have been reported in the literature. This paper derives such analytical closed-form expressions, pertaining to centered space-vector PWM (CSVPWM) and eight different advanced bus-clamping PWM (ABCPWM) schemes, for a three-level neutral-point-clamped (NPC) inverter. These ABCPWM schemes switch each phase at twice the nominal switching frequency in certain intervals of the line cycle while clamping each phase to one of the dc terminals over certain other intervals. The harmonic spectra of the output voltages, corresponding to the eight ABCPWM schemes, are studied and compared experimentally with that of CSVPWM over the entire modulation range. The measured values of weighted total harmonic distortion (WTHD) of the line voltage V-WTHD are used to validate the analytical closed-form expressions derived. The analytical expressions, pertaining to two of the ABCPWM methods, are also validated by measuring the total harmonic distortion (THD) in the line current I-THD on a 2.2-kW constant volts-per-hertz induction motor drive.

Cubic Sieve Congruence of the Discrete Logarithm Problem, and fractional part sequences

The Cubic Sieve Method for solving the Discrete Logarithm Problem in prime fields requires a nontrivial solution to the Cubic Sieve Congruence (CSC) x(3) equivalent to y(2)z (mod p), where p is a given prime number. A nontrivial solution must also satisfy x(3) not equal y(2)z and 1 <= x, y, z < p(alpha), where alpha is a given real number such that 1/3 < alpha <= 1/2. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC. CSC can be parametrized as x equivalent to v(2)z (mod p) and y equivalent to v(3)z (mod p). In this paper, we give a deterministic polynomial-time (O(ln(3) p) bit-operations) algorithm to determine, for a given v, a nontrivial solution to CSC, if one exists. Previously it took (O) over tilde (p(alpha)) time in the worst case to determine this. We relate the CSC problem to the gap problem of fractional part sequences, where we need to determine the non-negative integers N satisfying the fractional part inequality {theta N} < phi (theta and phi are given real numbers). The correspondence between the CSC problem and the gap problem is that determining the parameter z in the former problem corresponds to determining N in the latter problem. We also show in the alpha = 1/2 case of CSC that for a certain class of primes the CSC problem can be solved deterministically in <(O)over tilde>(p(1/3)) time compared to the previous best of (O) over tilde (p(1/2)). It is empirically observed that about one out of three primes is covered by the above class. (C) 2013 Elsevier B.V. All rights reserved.

Use of a structural alphabet to find compatible folds for amino acid sequences

The structural annotation of proteins with no detectable homologs of known 3D structure identified using sequence-search methods is a major challenge today. We propose an original method that computes the conditional probabilities for the amino-acid sequence of a protein to fit to known protein 3D structures using a structural alphabet, known as Protein Blocks (PBs). PBs constitute a library of 16 local structural prototypes that approximate every part of protein backbone structures. It is used to encode 3D protein structures into 1D PB sequences and to capture sequence to structure relationships. Our method relies on amino acid occurrence matrices, one for each PB, to score global and local threading of query amino acid sequences to protein folds encoded into PB sequences. It does not use any information from residue contacts or sequence-search methods or explicit incorporation of hydrophobic effect. The performance of the method was assessed with independent test datasets derived from SCOP 1.75A. With a Z-score cutoff that achieved 95% specificity (i.e., less than 5% false positives), global and local threading showed sensitivity of 64.1% and 34.2%, respectively. We further tested its performance on 57 difficult CASP10 targets that had no known homologs in PDB: 38 compatible templates were identified by our approach and 66% of these hits yielded correctly predicted structures. This method scales-up well and offers promising perspectives for structural annotations at genomic level. It has been implemented in the form of a web-server that is freely available at http://www.bo-protscience.fr/forsa.

NrichD database: sequence databases enriched with computationally designed protein-like sequences aid in remote homology detection

NrichD ( ext-link-type=''uri'' xlink:href=''http://proline.biochem.iisc.ernet.in/NRICHD/'' xlink:type=''simple''>http://proline.biochem.iisc.ernet.in/NRICHD/)< /named-content> is a database of computationally designed protein-like sequences, augmented into natural sequence databases that can perform hops in protein sequence space to assist in the detection of remote relationships. Establishing protein relationships in the absence of structural evidence or natural `intermediately related sequences' is a challenging task. Recently, we have demonstrated that the computational design of artificial intermediary sequences/linkers is an effective approach to fill naturally occurring voids in protein sequence space. Through a large-scale assessment we have demonstrated that such sequences can be plugged into commonly employed search databases to improve the performance of routinely used sequence search methods in detecting remote relationships. Since it is anticipated that such data sets will be employed to establish protein relationships, two databases that have already captured these relationships at the structural and functional domain level, namely, the SCOP database and the Pfam database, have been `enriched' with these artificial intermediary sequences. NrichD database currently contains 3 611 010 artificial sequences that have been generated between 27 882 pairs of families from 374 SCOP folds. The data sets are freely available for download. Additional features include the design of artificial sequences between any two protein families of interest to the user.

Structural characterization of folded and extended conformations in peptides containing gamma amino acids with proteinogenic side chains: crystal structures of gamma(n), (alpha gamma)(n) and gamma gamma delta gamma sequences

The crystal structures of nine peptides containing gamma(4)Val and gamma(4)Leu are described. The short sequences Boc-gamma(4)(R)Val](2)-OMe 1, Boc-gamma(4)(R)Val](3)-NHMe 2 and Boc-gamma(4)(S)Val-gamma(4)(R)Val-OMe 3 adopt extended apolar, sheet like structures. The tetrapeptide Boc-gamma(4)(R)Val](4)-OMe 4 adopts an extended conformation, in contrast to the folded C-14 helical structure determined previously for Boc-gamma(4)(R)Leu](4)-OMe. The hybrid alpha gamma sequence Boc-Ala-gamma(4)(R)Leu](2)-OMe 5 adopts an S-shaped structure devoid of intramolecular hydrogen bonds, with both alpha residues adopting local helical conformations. In sharp contrast, the tetrapeptides Boc-Aib-gamma(4)(S)Leu](2)-OMe 6 and Boc-Leu-gamma(4)(R)Leu](2)-OMe 7 adopt folded structures stabilized by two successive C-12 hydrogen bonds. gamma(4)Val residues have also been incorporated into the strand segments of a crystalline octapeptide, Boc-Leu-gamma(4)(R)Val-Val-(D)Pro-Gly-Leu-gamma(4)(R)Val-Val-OMe 8. The gamma gamma delta gamma tetrapeptide containing gamma(4)Val and delta(5)Leu residues adopts an extended sheet like structure. The hydrogen bonding pattern at gamma residues corresponds to an apolar sheet, while a polar sheet is observed at the lone delta residue. The transition between folded and extended structures at gamma residues involves a change of the torsion angle from the gauche to the trans conformation about the C-beta-C-alpha bond.

Microhomology-mediated end joining is the principal mediator of double-strand break repair during mitochondrial DNA lesions

Mitochondrial DNA (mtDNA) deletions are associated with various mitochondrial disorders. The deletions identified in humans are flanked by short, directly repeated mitochondrial DNA sequences; however, the mechanism of such DNA rearrangements has yet to be elucidated. In contrast to nuclear DNA (nDNA), mtDNA is more exposed to oxidative damage, which may result in double-strand breaks (DSBs). Although DSB repair in nDNA is well studied, repair mechanisms in mitochondria are not characterized. In the present study, we investigate the mechanisms of DSB repair in mitochondria using in vitro and ex vivo assays. Whereas classical NHEJ (C-NHEJ) is undetectable, microhomology-mediated alternative NHEJ efficiently repairs DSBs in mitochondria. Of interest, robust microhomology-mediated end joining (MMEJ) was observed with DNA substrates bearing 5-, 8-, 10-, 13-, 16-, 19-, and 22-nt microhomology. Furthermore, MMEJ efficiency was enhanced with an increase in the length of homology. Western blotting, immunoprecipitation, and protein inhibition assays suggest the involvement of CtIP, FEN1, MRE11, and PARP1 in mitochondrial MMEJ. Knock-down studies, in conjunction with other experiments, demonstrated that DNA ligase III, but not ligase IV or ligase I, is primarily responsible for the final sealing of DSBs during mitochondrial MMEJ. These observations highlight the central role of MMEJ in maintenance of mammalian mitochondrial genome integrity and is likely relevant for deletions observed in many human mitochondrial disorders.

Discovering compressing serial episodes from event sequences

Most pattern mining methods yield a large number of frequent patterns, and isolating a small relevant subset of patterns is a challenging problem of current interest. In this paper, we address this problem in the context of discovering frequent episodes from symbolic time-series data. Motivated by the Minimum Description Length principle, we formulate the problem of selecting relevant subset of patterns as one of searching for a subset of patterns that achieves best data compression. We present algorithms for discovering small sets of relevant non-redundant episodes that achieve good data compression. The algorithms employ a novel encoding scheme and use serial episodes with inter-event constraints as the patterns. We present extensive simulation studies with both synthetic and real data, comparing our method with the existing schemes such as GoKrimp and SQS. We also demonstrate the effectiveness of these algorithms on event sequences from a composable conveyor system; this system represents a new application area where use of frequent patterns for compressing the event sequence is likely to be important for decision support and control.