19034554
SIMPROT: Using an empirically determined indel distribution in simulations of protein evolution
BackgroundGeneral protein evolution models help determine the baseline expectations for the evolution of sequences, and they have been extensively useful in sequence analysis and for the computer simulation of artificial sequence data sets.ResultsWe have developed a new method of simulating protein sequence evolution, including insertion and deletion (indel) events in addition to amino-acid substitutions. The simulation generates both the simulated sequence family and a true sequence alignment that captures the evolutionary relationships between amino acids from different sequences. Our statistical model for indel evolution is based on the empirical indel distribution determined by Qian and Goldstein. We have parameterized this distribution so that it applies to sequences diverged by varying evolutionary times and generalized it to provide flexibility in simulation conditions. Our method uses a Monte-Carlo simulation strategy, and has been implemented in a C++ program named Simprot.ConclusionSimprot will be useful for testing methods of analysis of protein sequence families particularly alignment methods, phylogenetic tree building, detection of recombination and horizontal gene transfer, and homology detection, where knowing the true course of sequence evolution is essential.
1069327
DWE: Discriminating Word Enumerator
MOTIVATION
Tissue-specific transcription factor binding sites give insight into tissue-specific transcription regulation.


RESULTS
We describe a word-counting-based tool for de novo tissue-specific transcription factor binding site discovery using expression information in addition to sequence information. We incorporate tissue-specific gene expression through gene classification to positive expression and repressed expression. We present a direct statistical approach to find overrepresented transcription factor binding sites in a foreground promoter sequence set against a background promoter sequence set. Our approach naturally extends to synergistic transcription factor binding site search. We find putative transcription factor binding sites that are overrepresented in the proximal promoters of liver-specific genes relative to proximal promoters of liver-independent genes. Our results indicate that binding sites for hepatocyte nuclear factors (especially HNF-1 and HNF-4) and CCAAT/enhancer-binding protein (C/EBPbeta) are the most overrepresented in proximal promoters of liver-specific genes. Our results suggest that HNF-4 has strong synergistic relationships with HNF-1, HNF-4 and HNF-3beta and with C/EBPbeta.


AVAILABILITY
Programs are available for use over the Web at http://rulai.cshl.edu/tools/dwe.
7234685
Mining ChIP-chip data for transcription factor and cofactor binding sites
MOTIVATION
Identification of single motifs and motif pairs that can be used to predict transcription factor localization in ChIP-chip data, and gene expression in tissue-specific microarray data.


RESULTS
We describe methodology to identify de novo individual and interacting pairs of binding site motifs from ChIP-chip data, using an algorithm that integrates localization data directly into the motif discovery process. We combine matrix-enumeration based motif discovery with multivariate regression to evaluate candidate motifs and identify motif interactions. When applied to the HNF localization data in liver and pancreatic islets, our methods produce motifs that are either novel or improved known motifs. All motif pairs identified to predict localization are further evaluated according to how well they predict expression in liver and islets and according to how conserved are the relative positions of their occurrences. We find that interaction models of HNF1 and CDP motifs provide excellent prediction of both HNF1 localization and gene expression in liver. Our results demonstrate that ChIP-chip data can be used to identify interacting binding site motifs.


AVAILABILITY
Motif discovery programs and analysis tools are available on request from the authors.
9459767
Fault diagnosis and logic debugging using Boolean satisfiability
Recent advances in Boolean satisfiability have made it an attractive engine for solving many digital very-large-scale-integration design problems. Although useful in many stages of the design cycle, fault diagnosis and logic debugging have not been addressed within a satisfiability-based framework. This work proposes a novel Boolean satisfiability-based method for multiple-fault diagnosis and multiple-design-error diagnosis in combinational and sequential circuits. A number of heuristics are presented that keep the method memory and run-time efficient. An extensive suite of experiments on large circuits corrupted with different types of faults and errors confirm its robustness and practicality. They also suggest that satisfiability captures significant characteristics of the problem of diagnosis and encourage novel research in satisfiability-based diagnosis as a complementary process to design verification.
12460438
Evaluation of cache consistency algorithm performance
As more computer systems turn to multiprocessing for improved performance, additional research is needed to evaluate and improve the performance of cache consistency protocols. In this study, we use trace-driven simulation to examine the performance of several consistency protocols, including some new adaptive protocols which have not been examined in prior research. This study uses a wider variety of traces than have been previously analyzed, including some production applications from a vector mini-supercomputer system, and presents a wider variety of analyses than have been previously presented for a given workload. We find that the sharing characteristics of application programs have a large bearing on the relative performance of the different protocols. Update-based protocols outperform invalidate-based protocols when accesses so shared data are highly interleaved among different processors (fine-grain sharing), while invalidate-based protocols are superior if one processor performs all accesses to shared data over long periods of time (coarse-grain sharing). Adaptive protocols provide the best overall performance across all applications; we present a new protocol called Update-Once, which yields the highest average performance. In even the best cases, however, estimated processor utilizations are unacceptably low due to the overhead to maintain consistent caches. To extract good performance from multiprocessor systems, existing application programs must be recoded to reduce sharing between processors.
5777300
Evaluating Associativity in CPU Caches
The authors present new and efficient algorithms for simulating alternative direct-mapped and set-associative caches and use them to quantify the effect of limited associativity on the cache miss ratio. They introduce an algorithm, forest simulation, for simulating alternative direct-mapped caches and generalize one, which they call all-associativity simulation, for simulating alternative direct-mapped, set-associative, and fully-associative caches. The authors find that although all-associativity simulation is theoretically less efficient than forest simulation or stack simulation (a commonly used simulation algorithm), in practice it is not much slower and allows the simulation of many more caches with a single pass through an address trace. The authors also provide data and insight into how varying associatively affects the miss ratio. >
14619099
Minerva: An Adaptive Subblock Coherence Protocol for Improved SMP Performance
We present a new cache protocol, Minerva, which allows the effective cache block size to vary dynamically. Minerva works using sector caches (also known as block/subblock caches). Cache consistency attributes (from the MESI set of states) are associated with each 4-byte word in the cache. Each block can itself have one of the attributes invalid, exclusive or shared. Each block also has a current subblock size, of 2k words and a confidence value for hysteresis. The subblock size is reevaluated every time there is an external access (read or invalidate) to the block. When a fetch miss occurs within a block, a subblock equal to the current subblock size is fetched. Note that the fetch may involve a gather operation, with various words coming from different sources; some of the words may already be present. 
 
Depending on the assumed cache sizes, block sizes, bus width, and bus timings, we find that Minerva reduces execution times by 19-40%, averaged over 12 test parallel programs. For a 64-bit wide bus, we find a consistent execution time reduction of around 30%. Our evaluation considers the utility of various other optimizations and considers the extra state bits required.
15422333
Two Methods for the Efficient Analysis of Memory Address Trace Data
The high cost of analyzing long memory address traces has limited most researchers to short traces and analysis algorithms that are linear in the length of the trace. We suggest two methods that permit a trace to be shortened in length by one to two orders of magnitude (or more) for later further analysis. The Stack Deletion Method eliminates all references in the trace to the top k levels of the LRU stack. The Snapshot Method records the reference bits of the pages in the original tape at discrete intervals and uses these bits to generate a new trace. Extensive measurements are presented, from which we conclude that there is little or no loss in accuracy using reduced traces for many purposes for a wide range of memory sizes and degrees of reduction.