Search NASA⌕ Search

Engineering topics

Liang, S.

Publications and source records attributed to Liang, S..

7 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2004

cWINNOWER algorithm for finding fuzzy dna motifs

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4). Copyright Imperial College Press.

Evaluation Studies↗
NASA NTRS2003

Second Law of Thermodynamics Applied to Metabolic Networks

We present a simple algorithm based on linear programming, that combines Kirchoff's flux and potential laws and applies them to metabolic networks to predict thermodynamically feasible reaction fluxes. These law's represent mass conservation and energy feasibility that are widely used in electrical circuit analysis. Formulating the Kirchoff's potential law around a reaction loop in terms of the null space of the stoichiometric matrix leads to a simple representation of the law of entropy that can be readily incorporated into the traditional flux balance analysis without resorting to non-linear optimization. Our technique is new as it can easily check the fluxes got by applying flux balance analysis for thermodynamic feasibility and modify them if they are infeasible so that they satisfy the law of entropy. We illustrate our method by applying it to the network dealing with the central metabolism of Escherichia coli. Due to its simplicity this algorithm will be useful in studying large scale complex metabolic networks in the cell of different organisms.

Nigam, R.↗
NASA NTRS2002

Normalized Cut Algorithm for Automated Assignment of Protein Domains

We present a novel computational method for automatic assignment of protein domains from structural data. At the core of our algorithm lies a recently proposed clustering technique that has been very successful for image-partitioning applications. This grap.,l-theory based clustering method uses the notion of a normalized cut to partition. an undirected graph into its strongly-connected components. Computer implementation of our method tested on the standard comparison set of proteins from the literature shows a high success rate (84%), better than most existing alternative In addition, several other features of our algorithm, such as reliance on few adjustable parameters, linear run-time with respect to the size of the protein and reduced complexity compared to other graph-theory based algorithms, would make it an attractive tool for structural biologists.

Samanta, M. P.↗
NASA NTRS2001

Balanced Branching in Transcription Termination

The theory of stochastic transcription termination based on free-energy competition requires two or more reaction rates to be delicately balanced over a wide range of physical conditions. A large body of work on glasses and large molecules suggests that this should be impossible in such a large system in the absence of a new organizing principle of matter. We review the experimental literature of termination and find no evidence for such a principle but many troubling inconsistencies, most notably anomalous memory effects. These suggest that termination has a deterministic component and may conceivably be not stochastic at all. We find that a key experiment by Wilson and von Hippel allegedly refuting deterministic termination was an incorrectly analyzed regulatory effect of Mg(2+) binding.

Harrington, K. J.↗
NASA NTRS2000

Balanced Branching in Transcription Termination

The theory of stochastic transcription termination based on free-energy competition requires two or more reaction rates to be delicately balanced over a wide range of physical conditions. A large body of work on glasses and large molecules suggests that this should be impossible in such a large system in the absence of a new organizing principle of matter. We review the experimental literature of termination and find no evidence for such a principle but many troubling inconsistencies, most notably anomalous memory effects. These suggest that term ination has a deterministic component and may conceivably be not stochastic at all. We find that a key experiment by Wilson and von Hippel allegedly refuting deterministic termination was an incorrectly analyzed regulatory effect of Mg(2+) binding.

Harrington, K. J.↗
NASA NTRS2000

Balanced Branching in Transcription Termination

The theory of stochastic transcription termination based on free-energy competition [von Hippel, P. H. & Yager, T. D. (1992) Science 255,809-812 and van Hippel, P. H. & Yager, T. D. (1991) Proc. Natl. Acad. Sci. USA 88, 2307-2311] requires two or more reaction rates to be delicately balanced over a wide range of physical conditions. A large body of work on glasses and large molecules suggests that this balancing should be impossible in such a large system in the absence of a new organizing principle of matter. We review the experimental literature of termination and find no evidence for such a principle, but do find many troubling Inconsistencies, most notably, anomalous memory effects. These effects suggest that termination has a deterministic component and may conceivably not be stochastic at all. We find that a key experiment by Wilson and von Hippel [Wilson, K. S. & von Hippel, P. H. (1994) J. Mol. Biol. 244,36-51] thought to demonstrate stochastic termination was an incorrectly analyzed regulatory effect of Mg(2+) binding.

Harrington, K. J.↗