Resilient Wireless Sensor Networks Using Topology Control: A Review

Wireless sensor networks (WSNs) may be deployed in failure-prone environments, and WSNs nodes easily fail due to unreliable wireless connections, malicious attacks and resource-constrained features. Nevertheless, if WSNs can tolerate at most losing k − 1 nodes while the rest of nodes remain connected, the network is called k − connected. k is one of the most important indicators for WSNs’ self-healing capability. Following a WSN design flow, this paper surveys resilience issues from the topology control and multi-path routing point of view. This paper provides a discussion on transmission and failure models, which have an important impact on research results. Afterwards, this paper reviews theoretical results and representative topology control approaches to guarantee WSNs to be k − connected at three different network deployment stages: pre-deployment, post-deployment and re-deployment. Multi-path routing protocols are discussed, and many NP-complete or NP-hard problems regarding topology control are identified. The challenging open issues are discussed at the end. This paper can serve as a guideline to design resilient WSNs.

Development of a sensorimotor algorithm able to deal with unforeseen pushes and its implementation based on VHDL

Development of a Sensorimotor Algorithm Able to Deal with Unforeseen Pushes and Its Implementation Based on VHDL is the title of my thesis which concludes my Bachelor Degree in the Escuela Técnica Superior de Ingeniería y Sistemas de Telecomunicación of the Universidad Politécnica de Madrid. It encloses the overall work I did in the Neurorobotics Research Laboratory from the Beuth Hochschule für Technik Berlin during my ERASMUS year in 2015. This thesis is focused on the field of robotics, specifically an electronic circuit called Cognitive Sensorimotor Loop (CSL) and its control algorithm based on VHDL hardware description language. The reason that makes the CSL special resides in its ability to operate a motor both as a sensor and an actuator. This way, it is possible to achieve a balanced position in any of the robot joints (e.g. the robot manages to stand) without needing any conventional sensor. In other words, the back electromotive force (EMF) induced by the motor coils is measured and the control algorithm responds depending on its magnitude. The CSL circuit contains mainly an analog-to-digital converter (ADC) and a driver. The ADC consists on a delta-sigma modulation which generates a series of bits with a certain percentage of 1's and 0's, proportional to the back EMF. The control algorithm, running in a FPGA, processes the bit frame and outputs a signal for the driver. This driver, which has an H bridge topology, gives the motor the ability to rotate in both directions while it's supplied with the power needed. The objective of this thesis is to document the experiments and overall work done on push ignoring contractive sensorimotor algorithms, meaning sensorimotor algorithms that ignore large magnitude forces (compared to gravity) applied in a short time interval on a pendulum system. This main objective is divided in two sub-objectives: (1) developing a system based on parameterized thresholds and (2) developing a system based on a push bypassing filter. System (1) contains a module that outputs a signal which blocks the main Sensorimotor algorithm when a push is detected. This module has several different parameters as inputs e.g. the back EMF increment to consider a force as a push or the time interval between samples. System (2) consists on a low-pass Infinite Impulse Response digital filter. It cuts any frequency considered faster than a certain push oscillation. This filter required an intensive study on how to implement some functions and data types (fixed or floating point data) not supported by standard VHDL packages. Once this was achieved, the next challenge was to simplify the solution as much as possible, without using non-official user made packages. Both systems behaved with a series of interesting advantages and disadvantages for the elaboration of the document. Stability, reaction time, simplicity or computational load are one of the many factors to be studied in the designed systems. RESUMEN. Development of a Sensorimotor Algorithm Able to Deal with Unforeseen Pushes and Its Implementation Based on VHDL es un Proyecto de Fin de Grado (PFG) que concluye mis estudios en la Escuela Técnica Superior de Ingeniería y Sistemas de Telecomunicación de la Universidad Politécnica de Madrid. En él se documenta el trabajo de investigación que realicé en el Neurorobotics Research Laboratory de la Beuth Hochschule für Technik Berlin durante el año 2015 mediante el programa de intercambio ERASMUS. Este PFG se centra en el campo de la robótica y en concreto en un circuito electrónico llamado Cognitive Sensorimotor Loop (CSL) y su algoritmo de control basado en lenguaje de modelado hardware VHDL. La particularidad del CSL reside en que se consigue que un motor haga las veces tanto de sensor como de actuador. De esta manera es posible que las articulaciones de un robot alcancen una posición de equilibrio (p.ej. el robot se coloca erguido) sin la necesidad de sensores en el sentido estricto de la palabra. Es decir, se mide la propia fuerza electromotriz (FEM) inducida sobre el motor y el algoritmo responde de acuerdo a su magnitud. El circuito CSL se compone de un convertidor analógico-digital (ADC) y un driver. El ADC consiste en un modulador sigma-delta, que genera una serie de bits con un porcentaje de 1's y 0's determinado, en proporción a la magnitud de la FEM inducida. El algoritmo de control, que se ejecuta en una FPGA, procesa esta cadena de bits y genera una señal para el driver. El driver, que posee una topología en puente H, provee al motor de la potencia necesaria y le otorga la capacidad de rotar en cualquiera de las dos direcciones. El objetivo de este PFG es documentar los experimentos y en general el trabajo realizado en algoritmos Sensorimotor que puedan ignorar fuerzas de gran magnitud (en comparación con la gravedad) y aplicadas en una corta ventana de tiempo. En otras palabras, ignorar empujones conservando el comportamiento original frente a la gravedad. Para ello se han desarrollado dos sistemas: uno basado en umbrales parametrizados (1) y otro basado en un filtro de corte ajustable (2). El sistema (1) contiene un módulo que, en el caso de detectar un empujón, genera una señal que bloquea el algoritmo Sensorimotor. Este módulo recibe diferentes parámetros como el incremento necesario de la FEM para que se considere un empujón o la ventana de tiempo para que se considere la existencia de un empujón. El sistema (2) consiste en un filtro digital paso-bajo de respuesta infinita que corta cualquier variación que considere un empujón. Para crear este filtro se requirió un estudio sobre como implementar ciertas funciones y tipos de datos (coma fija o flotante) no soportados por las librerías básicas de VHDL. Tras esto, el objetivo fue simplificar al máximo la solución del problema, sin utilizar paquetes de librerías añadidos. En ambos sistemas aparecen una serie de ventajas e inconvenientes de interés para el documento. La estabilidad, el tiempo de reacción, la simplicidad o la carga computacional son algunas de las muchos factores a estudiar en los sistemas diseñados. Para concluir, también han sido documentadas algunas incorporaciones a los sistemas: una interfaz visual en VGA, un módulo que compensa el offset del ADC o la implementación de una batería de faders MIDI entre otras.

Additional evidence for an eight-transmembrane-domain topology for Caenorhabditis elegans and human presenilins

Presenilins have been implicated in the genesis of Alzheimer’s disease and in facilitating LIN-12/Notch activity during development. All presenilins have multiple hydrophobic regions that could theoretically span a membrane, and a description of the membrane topology is a crucial step toward deducing the mechanism of presenilin function. Previously, we proposed an eight-transmembrane-domain model for presenilin, based on studies of the Caenorhabditis elegans SEL-12 presenilin. Here, we describe experiments that support the view that two of the hydrophobic regions of SEL-12 function as the seventh and eighth transmembrane domains. Furthermore, we have shown that human presenilin 1 behaves like SEL-12 presenilin when analyzed by our methods. Our results provide additional experimental support for the eight-transmembrane-domain model of presenilin topology.

Semantic Support for Computational Land-Use Modelling

Postprint

Transmembrane topology of a CLC chloride channel

CLC chloride channels form a large and conserved gene family unrelated to other channel proteins. Knowledge of the transmembrane topology of these channels is important for understanding the effects of mutations found in human myotonia and inherited hypercalciuric kidney stone diseases and for the interpretation of structure–function studies. We now systematically study the topology of human ClC-1, a prototype CLC channel that is defective in human myotonia. Using a combination of in vitro glycosylation scanning and protease protection assays, we show that both N and C termini face the cytoplasm and demonstrate the presence of 10 (or less likely 12) transmembrane spans. Difficult regions were additionally tested by inserting cysteines and probing the effect of cysteine-modifying reagents on ClC-1 currents. The results show that D3 crosses the membrane and D4 does not, and that L549 between D11 and D12 is accessible from the outside. Further, since the modification of cysteines introduced between D11 and D12 and at the extracellular end of D3 strongly affect ClC-1 currents, these regions are suggested to be important for ion permeation.

Structure and function in rhodopsin: Topology of the C-terminal polypeptide chain in relation to the cytoplasmic loops*

Cysteine mutagenesis and site-directed spin labeling in the C-terminal region of rhodopsin have been used to probe the local structure and proximity of that region to the cytoplasmic loops. Each of the native amino acids in the sequence T335–T340 was replaced with Cys, one at a time. The sulfhydryl groups of all mutants reacted rapidly with the sulfhydryl reagent 4,4′-dithiodipyridine, which indicated a high degree of solvent accessibility. Furthermore, to probe the proximity relationships, a series of double Cys mutants was constructed. One Cys in all sets was at position 338 and the other was at a position in the sequence S240–V250 in the EF interhelical loop, at position 65 in the AB interhelical loop, or at position 140 in the CD interhelical loop. In the dark state, no significant disulfide formation was observed between C338 and C65 or C140 under the conditions used, whereas a relatively rapid disulfide formation was observed between C338 and C242 or C245. Spin labels in the double Cys mutants showed the strongest magnetic interactions between the nitroxides attached to C338 and C245 or C246. Light activation of the double mutant T242C/S338C resulted in slower disulfide formation, whereas interactions between nitroxides at C338 and C245 or C246 decreased. These results suggest the proximity of the C-terminal residue C338 to residues located on the outer face of a cytoplasmic helical extension of the F helix with an apparent increase of distance upon photoactivation.

Cells that register logical relationships among proteins

Two-hybrid methods have augmented the classical genetic techniques biologists use to assign function to genes. Here, we describe construction of a two-bait interaction trap that uses yeast cells to register more complex protein relationships than those detected in existing two-hybrid systems. We show that such cells can identify bridge or connecting proteins and peptide aptamers that discriminate between closely related allelic variants. The protein relationships detected by these cells are analogous to classical genetic relationships, but lend themselves to systematic application to the products of entire genomes and combinatorial libraries. We show that, by performing logical operations on the phenotypic outputs of these complex cells and existing two-hybrid cells, we can make inferences about the topology and order of protein interactions. Finally, we show that cells that register such relationships can perform logical operations on protein inputs. Thus these cells will be useful for analysis of gene and allele function, and may also define a path for construction of biological computational devices.

Estimating the probability for a protein to have a new fold: A statistical computational model

Structural genomics aims to solve a large number of protein structures that represent the protein space. Currently an exhaustive solution for all structures seems prohibitively expensive, so the challenge is to define a relatively small set of proteins with new, currently unknown folds. This paper presents a method that assigns each protein with a probability of having an unsolved fold. The method makes extensive use of protomap, a sequence-based classification, and scop, a structure-based classification. According to protomap, the protein space encodes the relationship among proteins as a graph whose vertices correspond to 13,354 clusters of proteins. A representative fold for a cluster with at least one solved protein is determined after superposition of all scop (release 1.37) folds onto protomap clusters. Distances within the protomap graph are computed from each representative fold to the neighboring folds. The distribution of these distances is used to create a statistical model for distances among those folds that are already known and those that have yet to be discovered. The distribution of distances for solved/unsolved proteins is significantly different. This difference makes it possible to use Bayes' rule to derive a statistical estimate that any protein has a yet undetermined fold. Proteins that score the highest probability to represent a new fold constitute the target list for structural determination. Our predicted probabilities for unsolved proteins correlate very well with the proportion of new folds among recently solved structures (new scop 1.39 records) that are disjoint from our original training set.

Transition-state structure as a unifying basis in protein-folding mechanisms: Contact order, chain topology, stability, and the extended nucleus mechanism

I attempt to reconcile apparently conflicting factors and mechanisms that have been proposed to determine the rate constant for two-state folding of small proteins, on the basis of general features of the structures of transition states. Φ-Value analysis implies a transition state for folding that resembles an expanded and distorted native structure, which is built around an extended nucleus. The nucleus is composed predominantly of elements of partly or well-formed native secondary structure that are stabilized by local and long-range tertiary interactions. These long-range interactions give rise to connecting loops, frequently containing the native loops that are poorly structured. I derive an equation that relates differences in the contact order of a protein to changes in the length of linking loops, which, in turn, is directly related to the unfavorable free energy of the loops in the transition state. Kinetic data on loop extension mutants of CI2 and α-spectrin SH3 domain fit the equation qualitatively. The rate of folding depends primarily on the interactions that directly stabilize the nucleus, especially those in native-like secondary structure and those resulting from the entropy loss from the connecting loops, which vary with contact order. This partitioning of energy accounts for the success of some algorithms that predict folding rates, because they use these principles either explicitly or implicitly. The extended nucleus model thus unifies the observations of rate depending on both stability and topology.

How does a β-hairpin fold/unfold? Competition between topology and heterogeneity in a solvable model

We study the competition between topological effects and sequence inhomogeneities in determining the thermodynamics and the un/folding kinetics of a β-hairpin. Our work utilizes a new exactly solvable model that allows for arbitrary configurations of native contacts. In general, the competition between heterogeneity and topology results in a crossover of the dominant transition state. Interestingly, near this crossover, the single reaction coordinate picture can be seriously misleading. Our results also suggest that inferring the folding pathway from unfolding simulations is not always justified.

Temperature, template topology, and factor requirements of archaeal transcription

Although Archaea are prokaryotic and resemble Bacteria morphologically, their transcription apparatus is remarkably similar to those of eukaryotic cell nuclei. Because some Archaea exist in environments with temperatures of around 100°C, they are likely to have evolved unique strategies for transcriptional control. Here, we investigate the effects of temperature and DNA template topology in a thermophilic archaeal transcription system. Significantly, and in marked contrast with characterized eucaryal systems, archaeal DNA template topology has negligible effect on transcription levels at physiological temperatures using highly purified polymerase and recombinant transcription factors. Furthermore, archaeal transcription does not require hydrolysis of the β-γ phosphoanhydride bond of ATP. However, at lower temperatures, negatively supercoiled templates are transcribed more highly than those that are positively supercoiled. Notably, the block to transcription on positively supercoiled templates at lowered temperatures is at the level of polymerase binding and promoter opening. These data imply that Archaea do not possess a functional homologue of transcription factor TFIIH, and that for the promoters studied, transcription is mediated by TATA box-binding protein, transcription factor TFB, and RNA polymerase alone. Furthermore, they suggest that the reduction of plasmid linking number by hyperthermophilic Archaea in vivo in response to cold shock is a mechanism to maintain gene expression under these adverse circumstances.

Topology of allosteric regulation of lactose permease

Sugar transport by some permeases in Escherichia coli is allosterically regulated by the phosphorylation state of the intracellular regulatory protein, enzyme IIAglc of the phosphoenolpyruvate:sugar phosphotransferase system. A sensitive radiochemical assay for the interaction of enzyme IIAglc with membrane-associated lactose permease was used to characterize the binding reaction. The binding is stimulated by transportable substrates such as lactose, melibiose, and raffinose, but not by sugars that are not transported (maltose and sucrose). Treatment of lactose permease with N-ethylmaleimide, which blocks ligand binding and transport by alkylating Cys-148, also blocks enzyme IIAglc binding. Preincubation with the substrate analog β-d-galactopyranosyl 1-thio-β-d-galactopyranoside protects both lactose transport and enzyme IIAglc binding against inhibition by N-ethylmaleimide. A collection of lactose permease replacement mutants at Cys-148 showed, with the exception of C148V, a good correlation of relative transport activity and enzyme IIAglc binding. The nature of the interaction of enzyme IIAglc with the cytoplasmic face of lactose permease was explored. The N- and C-termini, as well as five hydrophilic loops in the permease, are exposed on the cytoplasmic surface of the membrane and it has been proposed that the central cytoplasmic loop of lactose permease is the major determinant for interaction with enzyme IIAglc. Lactose permease mutants with polyhistidine insertions in cytoplasmic loops IV/V and VI/VII and periplasmic loop VII/VIII retain transport activity and therefore substrate binding, but do not bind enzyme IIAglc, indicating that these regions of lactose permease may be involved in recognition of enzyme IIAglc. Taken together, these results suggest that interaction of lactose permease with substrate promotes a conformational change that brings several cytoplasmic loops into an arrangement optimal for interaction with the regulatory protein, enzyme IIAglc. A topological map of the proposed interaction is presented.

GeneSplicer: a new computational method for splice site prediction

GeneSplicer is a new, flexible system for detecting splice sites in the genomic DNA of various eukaryotes. The system has been tested successfully using DNA from two reference organisms: the model plant Arabidopsis thaliana and human. It was compared to six programs representing the leading splice site detectors for each of these species: NetPlantGene, NetGene2, HSPL, NNSplice, GENIO and SpliceView. In each case GeneSplicer performed comparably to the best alternative, in terms of both accuracy and computational efficiency.

A fully automatic evolutionary classification of protein folds: Dali Domain Dictionary version 3

The Dali Domain Dictionary (http://www.ebi.ac.uk/dali/domain) is a numerical taxonomy of all known structures in the Protein Data Bank (PDB). The taxonomy is derived fully automatically from measurements of structural, functional and sequence similarities. Here, we report the extension of the classification to match the traditional four hierarchical levels corresponding to: (i) supersecondary structural motifs (attractors in fold space), (ii) the topology of globular domains (fold types), (iii) remote homologues (functional families) and (iv) homologues with sequence identity above 25% (sequence families). The computational definitions of attractors and functional families are new. In September 2000, the Dali classification contained 10 531 PDB entries comprising 17 101 chains, which were partitioned into five attractor regions, 1375 fold types, 2582 functional families and 3724 domain sequence families. Sequence families were further associated with 99 582 unique homologous sequences in the HSSP database, which increases the number of effectively known structures several-fold. The resulting database contains the description of protein domain architecture, the definition of structural neighbours around each known structure, the definition of structurally conserved cores and a comprehensive library of explicit multiple alignments of distantly related protein families.

Mechanism of topology simplification by type II DNA topoisomerases

Type II DNA topoisomerases actively reduce the fractions of knotted and catenated circular DNA below thermodynamic equilibrium values. To explain this surprising finding, we designed a model in which topoisomerases introduce a sharp bend in DNA. Because the enzymes have a specific orientation relative to the bend, they act like Maxwell's demon, providing unidirectional strand passage. Quantitative analysis of the model by computer simulations proved that it can explain much of the experimental data. The required sharp DNA bend was demonstrated by a greatly increased cyclization of short DNA fragments from topoisomerase binding and by direct visualization with electron microscopy.