@inproceedings{4581, abstract = {We have extended the software model checker BLAST to automatically generate test suites that guarantee full coverage with respect to a given predicate. More precisely, given a C program and a target predicate p, BLAST determines the set L of program locations which program execution can reach with p true, and automatically generates a set of test vectors that exhibit the truth of p at all locations in L. We have used BLAST to generate test suites and to detect dead code in C programs with up to 30 K lines of code. The analysis and test vector generation is fully automatic (no user intervention) and exact (no false positives).}, author = {Beyer, Dirk and Chlipala, Adam J and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {326 -- 335}, publisher = {IEEE}, title = {{Generating tests from counterexamples}}, doi = {10.1109/ICSE.2004.1317455}, year = {2004}, } @inproceedings{4629, abstract = {Temporal logic is two-valued: a property is either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic Ctl which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic Dctl over transition systems, Markov chains, and Markov decision processes. We present two semantics for Dctl: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for Dctl, and we provide model-checking algorithms for both semantics.}, author = {de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, pages = {77 -- 92}, publisher = {Springer}, title = {{Model checking discounted temporal properties}}, doi = {10.1007/978-3-540-24730-2_6}, volume = {2988}, year = {2004}, } @article{6155, abstract = {The genome of the nematode Caenorhabditis elegans encodes seven soluble guanylate cyclases (sGCs) [1]. In mammals, sGCs function as α/β heterodimers activated by gaseous ligands binding to a haem prosthetic group 2, 3. The principal activator is nitric oxide, which acts through sGCs to regulate diverse cellular events. In C. elegans the function of sGCs is mysterious: the worm genome does not appear to encode nitric oxide synthase, and all C. elegans sGC subunits are more closely related to mammalian β than α subunits [1]. Here, we show that two of the seven C. elegans sGCs, GCY-35 and GCY-36, promote aggregation behavior. gcy-35 and gcy-36 are expressed in a small number of neurons. These include the body cavity neurons AQR, PQR, and URX, which are directly exposed to the blood equivalent of C. elegans and regulate aggregation behavior [4]. We show that GCY-35 and GCY-36 act as α-like and β-like sGC subunits and that their function in the URX sensory neurons is sufficient for strong nematode aggregation. Neither GCY-35 nor GCY-36 is absolutely required for C. elegans to aggregate. Instead, these molecules may transduce one of several pathways that induce C. elegans to aggregate or may modulate aggregation by responding to cues in C. elegans body fluid.}, author = {Cheung, Benny H.H and Arellano-Carbajal, Fausto and Rybicki, Irene and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {12}, pages = {1105--1111}, publisher = {Elsevier}, title = {{Soluble guanylate cyclases act in neurons exposed to the body fluid to promote C. elegans aggregation behavior}}, doi = {10.1016/j.cub.2004.06.027}, volume = {14}, year = {2004}, } @article{7334, abstract = {Fundamental and phenomenological models for cells, stacks, and complete systems of PEFC and SOFC are reviewed and their predictive power is assessed by comparing model simulations against experiments. Computationally efficient models suited for engineering design include the (1+1) dimensionality approach, which decouples the membrane in-plane and through-plane processes, and the volume-averaged-method (VAM) that considers only the lumped effect of pre-selected system components. The former model was shown to capture the measured lateral current density inhomogeneities in a PEFC and the latter was used for the optimization of commercial SOFC systems. State Space Modeling (SSM) was used to identify the main reaction pathways in SOFC and, in conjunction with the implementation of geometrically well-defined electrodes, has opened a new direction for the understanding of electrochemical reactions. Furthermore, SSM has advanced the understanding of the COpoisoning-induced anode impedance in PEFC. Detailed numerical models such as the Lattice Boltzmann (LB) method for transport in porous media and the full 3-D Computational Fluid Dynamics (CFD) Navier-Stokes simulations are addressed. These models contain all components of the relevant physics and they can improve the understanding of the related phenomena, a necessary condition for the development of both appropriate simplified models as well as reliable technologies. Within the LB framework, a technique for the characterization and computer-reconstruction of the porous electrode structure was developed using advanced pattern recognition algorithms. In CFD modeling, 3-D simulations were used to investigate SOFC with internal methane steam reforming and have exemplified the significance of porous and novel fractal channel distributors for the fuel and oxidant delivery, as well as for the cooling of PEFC. As importantly, the novel concept has been put forth of functionally designed, fractal-shaped fuel cells, showing promise of significant performance improvements over the conventional rectangular shaped units. Thermo-economic modeling for the optimization of PEFC is finally addressed. }, author = {Mantzaras, John and Freunberger, Stefan Alexander and Büchi, Felix N. and Roos, Markus and Brandstätter, Wilhelm and Prestat, Michel and Gauckler, Ludwig J. and Andreaus, Bernhard and Hajbolouri, Faegheh and Senn, Stephan M. and Poulikakos, Dimos and Chaniotis, Andreas K. and Larrain, Diego and Autissier, Nordahl and Maréchal, François}, issn = {0009-4293}, journal = {CHIMIA International Journal for Chemistry}, number = {12}, pages = {857--868}, publisher = {Swiss Chemical Society}, title = {{Fuel cell modeling and simulations}}, doi = {10.2533/000942904777677029}, volume = {58}, year = {2004}, } @article{7333, abstract = {The analysis of the complete H2/air polymer electrolyte fuel cell system shows that process air humidification is one of the biggest obstacles for a high performance portable system in the kW range. Therefore, a new concept, with passive process air humidification integrated into the stack, has been developed. Humidification in each cell makes the process independent from the number of cells and the operation mode, thus making the concept fully scalable. Without external humidification the system is simpler, smaller, and cheaper. The humidification of the process air is achieved by transfer of product water from the exhaust air, through part of the membrane, to the dry intake air. Tests have shown that cells using the concept of internal humidification and operated with dry air at 70 ° have almost the same performance as when operated with external humidification. A 42‐cell stack with this internal humidification concept was built and integrated into a portable 1 kW power generator system.}, author = {Santis, M. and Schmid, D. and Ruge, M. and Freunberger, Stefan Alexander and Büchi, F.N.}, issn = {1615-6846}, journal = {Fuel Cells}, number = {3}, pages = {214--218}, publisher = {Wiley}, title = {{Modular stack-internal air humidification concept-verification in a 1 kW stack}}, doi = {10.1002/fuce.200400028}, volume = {4}, year = {2004}, } @article{864, abstract = {We present a method for prediction of functional sites in a set of aligned protein sequences. The method selects sites which are both well conserved and clustered together in space, as inferred from the 3D structures of proteins included in the alignment. We tested the method using 86 alignments from the NCBI CDD database, where the sites of experimentally determined ligand and/or macromolecular interactions are annotated. In agreement with earlier investigations, we found that functional site predictions are most successful when overall background sequence conservation is low, such that sites under evolutionary constraint become apparent. In addition, we found that averaging of conservation values across spatially clustered sites improves predictions under certain conditions: that is, when overall conservation is relatively high and when the site in question involves a large macromolecular binding interface. Under these conditions it is better to look for clusters of conserved sites than to look for particular conserved sites.}, author = {Panchenko, Anna R and Fyodor Kondrashov and Bryant, Stephen H}, journal = {Protein Science}, number = {4}, pages = {884 -- 892}, publisher = {Wiley-Blackwell}, title = {{Prediction of functional sites by analysis of sequence and structure conservation}}, doi = {10.1110/ps.03465504}, volume = {13}, year = {2004}, } @article{870, abstract = {Only a fraction of eukaryotic genes affect the phenotype drastically. We compared 18 parameters in 1273 human morbid genes, known to cause diseases, and in the remaining 16 580 unambiguous human genes. Morbid genes evolve more slowly, have wider phylogenetic distributions, are more similar to essential genes of Drosophila melanogaster, code for longer proteins containing more alanine and glycine and less histidine, lysine and methionine, possess larger numbers of longer introns with more accurate splicing signals and have higher and broader expressions. These differences make it possible to classify as non-morbid 34% of human genes with unknown morbidity, when only 5% of known morbid genes are incorrectly classified as non-morbid. This classification can help to identify disease-causing genes among multiple candidates.}, author = {Fyodor Kondrashov and Ogurtsov, Aleksey Yu and Kondrashov, Alexey S}, journal = {Nucleic Acids Research}, number = {5}, pages = {1731 -- 1737}, publisher = {Oxford University Press}, title = {{Bioinformatical assay of human gene morbidity}}, doi = {10.1093/nar/gkh330}, volume = {32}, year = {2004}, } @article{875, abstract = {The dominance of wild-type alleles and the concomitant recessivity of deleterious mutant alleles might have evolved by natural selection or could be a by-product of the molecular and physiological mechanisms of gene action. We compared the properties of human haplosufficient genes, whose wild-type alleles are dominant over loss-of-function alleles, with haploinsufficient (recessive wild-type) genes, which produce an abnormal phenotype when heterozygous for a loss-of-function allele. The fraction of haplosufficient genes is the highest among the genes that encode enzymes, which is best compatible with the physiological theory. Haploinsufficient genes, on average, have more paralogs than haplosufficient genes, supporting the idea that gene dosage could be important for the initial fixation of duplications. Thus, haplo(in)sufficiency of a gene and its propensity for duplication might have a common evolutionary basis.}, author = {Fyodor Kondrashov and Koonin, Eugene V}, journal = {Trends in Genetics}, number = {7}, pages = {287 -- 291}, publisher = {Elsevier}, title = {{A common framework for understanding the origin of genetic dominance and evolutionary fates of gene duplications}}, doi = {10.1016/j.tig.2004.05.001}, volume = {20}, year = {2004}, } @article{889, abstract = {The function of protein and RNA molecules depends on complex epistatic interactions between sites. Therefore, the deleterious effect of a mutation can be suppressed by a compensatory second-site substitution. In relating a list of 86 pathogenic mutations in human IRNAs encoded by mitochondrial genes to the sequences of their mammalian orthologs, we noted that 52 pathogenic mutations were present in normal tRNAs of one or several nonhuman mammals. We found at least five mechanisms of compensation for 32 pathogenic mutations that destroyed a Watson-Crick pair in one of the four tRNA stems: restoration of the affected Watson-Crick interaction (25 cases), strengthening of another pair (4 cases), creation of a new pair (8 cases), changes of multiple interactions in the affected stem (11 cases) and changes involving the interaction between the loop and stem structures (3 cases). A pathogenic mutation and its compensating substitution are fixed in a lineage in rapid succession, and often a compensatory interaction evolves convergently in different clades. At least 10%, and perhaps as many as 50%, of all nucleotide substitutions in evolving mammalian (RNAs participate in such interactions, indicating that the evolution of tRNAs proceeds along highly epistatic fitness ridges.}, author = {Kern, Andrew D and Fyodor Kondrashov}, journal = {Nature Genetics}, number = {11}, pages = {1207 -- 1212}, publisher = {Nature Publishing Group}, title = {{Mechanisms and convergence of compensatory evolution in mammalian mitochondrial tRNAs}}, doi = {10.1038/ng1451}, volume = {36}, year = {2004}, } @article{9493, abstract = {In a number of organisms, transgenes containing transcribed inverted repeats (IRs) that produce hairpin RNA can trigger RNA-mediated silencing, which is associated with 21-24 nucleotide small interfering RNAs (siRNAs). In plants, IR-driven RNA silencing also causes extensive cytosine methylation of homologous DNA in both the transgene "trigger" and any other homologous DNA sequences--"targets". Endogenous genomic sequences, including transposable elements and repeated elements, are also subject to RNA-mediated silencing. The RNA silencing gene ARGONAUTE4 (AGO4) is required for maintenance of DNA methylation at several endogenous loci and for the establishment of methylation at the FWA gene. Here, we show that mutation of AGO4 substantially reduces the maintenance of DNA methylation triggered by IR transgenes, but AGO4 loss-of-function does not block the initiation of DNA methylation by IRs. AGO4 primarily affects non-CG methylation of the target sequences, while the IR trigger sequences lose methylation in all sequence contexts. Finally, we find that AGO4 and the DRM methyltransferase genes are required for maintenance of siRNAs at a subset of endogenous sequences, but AGO4 is not required for the accumulation of IR-induced siRNAs or a number of endogenous siRNAs, suggesting that AGO4 may function downstream of siRNA production.}, author = {Zilberman, Daniel and Cao, Xiaofeng and Johansen, Lisa K. and Xie, Zhixin and Carrington, James C. and Jacobsen, Steven E.}, issn = {1879-0445}, journal = {Current Biology}, number = {13}, pages = {1214--1220}, publisher = {Elsevier}, title = {{Role of Arabidopsis ARGONAUTE4 in RNA-directed DNA methylation triggered by inverted repeats}}, doi = {10.1016/j.cub.2004.06.055}, volume = {14}, year = {2004}, }