Density estimation is a building block for many other statistical methods, such as classification, nonparametric testing, and data compression. In this paper, we focus on a non-parametric approach to multivariate density estimation, and study its asymptotic properties under both frequentist and Bayesian settings. The estimated density function is obtained by considering a sequence of approximating spaces to the space of densities. These spaces consist of piecewise constant density functions supported by binary partitions with increasing complexity. To obtain an estimate, the partition is learned by maximizing either the likelihood of the corresponding histogram on that partition, or the marginal posterior probability of the partition under a suitable prior. We analyze the convergence rate of the maximum likelihood estimator and the posterior concentration rate of the Bayesian estimator, and conclude that for a relatively rich class of density functions the rate does not directly depend on the dimension. We also show that the Bayesian method can adapt to the unknown smoothness of the density function. The method is applied to several specific function classes and explicit rates are obtained. These include spatially sparse functions, functions of bounded variation, and Hölder continuous functions. We also introduce an ensemble approach, obtained by aggregating multiple density estimates fit under carefully designed perturbations, and show that for density functions lying in a Hölder space ($\mathcal{H}^{1, \beta}, 0 < \beta \leq 1$), the ensemble method can achieve minimax convergence rate up to a logarithmic term, while the corresponding rate of the density estimator based on a single partition is suboptimal for this function class.

Deciphering the free energy landscape of biomolecular structure space is crucial for understanding many complex molecular processes, such as protein-protein interaction, RNA folding, and protein folding. A major source of current dynamic structure data is Molecular Dynamics (MD) simulations. Several methods have been proposed to investigate the free energy landscape from MD data, but all of them rely on the assumption that kinetic similarity is associated with global geometric similarity, which may lead to unsatisfactory results. In this paper, we proposed a new method called Conditional Angle Partition Tree to reveal the hierarchical free energy landscape by correlating local geometric similarity with kinetic similarity. Its application on the benchmark alanine dipeptide MD data showed a much better performance than existing methods in exploring and understanding the free energy landscape. We also applied it to the MD data of Villin HP35. Our results are more reasonable on various aspects than those from other methods and very informative on the hierarchical structure of its energy landscape.

MOTIVATION: Isoform deconvolution is an NP-hard problem. The accuracy of the proposed solutions is far from perfect. At present, it is not known if gene structure and isoform concentration can be uniquely inferred given paired-end reads, and there is no objective method to select the fragment length to improve the number of identifiable genes. Different pieces of evidence suggest that the optimal fragment length is gene-dependent, stressing the need for a method that selects the fragment length according to a reasonable trade-off across all the genes in the whole genome. RESULTS: A gene is considered to be identifiable if it is possible to get both the structure and concentration of its transcripts univocally. Here, we present a method to state the identifiability of this deconvolution problem. Assuming a given transcriptome and that the coverage is sufficient to interrogate all junction reads of the transcripts, this method states whether or not a gene is identifiable given the read length and fragment length distribution. Applying this method using different read and fragment length combinations, the optimal average fragment length for the human transcriptome is around 400-600 nt for coding genes and 150-200 nt for long non-coding RNAs. The optimal read length is the largest one that fits in the fragment length. It is also discussed the potential profit of combining several libraries to reconstruct the transcriptome. Combining two libraries of very different fragment lengths results in a significant improvement in gene identifiability. AVAILABILITY AND IMPLEMENTATION: Code is available in GitHub (https://github.com/JFerrer-B/transcriptome-identifiability). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Multi-omics data allow us to select a small set of informative markers for the discrimination of specific cell types and study of cellular heterogeneity. However, it is often challenging to choose an optimal marker panel from the high-dimensional molecular profiles for a large amount of cell types. Here, we propose a method called Mixed Integer programming Model to Identify Cell type-specific marker panel (MIMIC). MIMIC maintains the hierarchical topology among different cell types and simultaneously maximizes the specificity of a fixed number of selected markers. MIMIC was benchmarked on the mouse ENCODE RNA-seq dataset, with 29 diverse tissues, for 43 surface markers (SMs) and 1345 transcription factors (TFs). MIMIC could select biologically meaningful markers and is robust for different accuracy criteria. It shows advantages over the standard single gene-based approaches and widely used dimensional reduction methods, such as multidimensional scaling and t-SNE, both in accuracy and in biological interpretation. Furthermore, the combination of SMs and TFs achieves better specificity than SMs or TFs alone. Applying MIMIC to a large collection of 641 RNA-seq samples covering 231 cell types identifies a panel of TFs and SMs that reveal the modularity of cell type association networks. Finally, the scalability of MIMIC is demonstrated by selecting enhancer markers from mouse ENCODE data. MIMIC is freely available at https://github.com/MengZou1/MIMIC.

Deep neural networks (DNNs) are recently found to be vulnerable to JPEG compression artifacts, which distort the feature representations of DNNs leading to serious accuracy degradation. Most existing training methods which aim to address this problem add compressed images to the training data to enhance the robustness of DNNs. However, their improvements are limited since these methods usually regard the compressed images as new training samples instead of distorted samples. The feature distortions between the raw images and the compressed images are not investigated. In this work, we propose a new training method, called Feature Consistency Training, that is designed to minimize the feature distortions caused by JPEG artifacts. At each training iteration, we simultaneously input a raw image and its compressed version with a randomly sampled quality into a DNN model and extract the features from the internal layers. By adding feature consistency constraint to the objective function, the feature distortions in the representation space are minimized in order to learn robust filters. Besides, we present a residual mapping block which takes the quality factor of the compressed image as an additional information to further reduce the feature distortion. Extensive experiments demonstrate that our method outperforms several existed training methods on JPEG compressed images. Furthermore, DNN models trained by our method are found to be more robust to unseen distortions.

Head pose estimation has attracted immense research interest recently, as its inherent information significantly improves the performance of face-related applications such as face alignment and face recognition. In this paper, we conduct an in-depth study of head pose estimation and present a multiregression loss function, an L2 regression loss combined with an ordinal regression loss, to train a convolutional neural network (CNN) that is dedicated to estimating head poses from RGB images without depth information. The ordinal regression loss is utilized to address the nonstationary property observed as the facial features change with respect to different head pose angles and learn robust features. The L2 regression loss leverages these features to provide precise angle predictions for input images. To avoid the ambiguity problem in the commonly used Euler angle representation, we further formulate the head pose estimation problem in quaternions. Our quaternion-based multiregression loss method achieves state-of-the-art performance on the AFLW2000, AFLW test set, and AFW datasets and is closing the gap with methods that utilize depth information on the BIWI dataset.

Diabetic retinopathy is the primary cause of blindness in the working-age population of the developed world. Diagnosing the disease heavily relies on imaging studies, which is a time consuming and a manual process performed by trained clinicians. Enhancing the accuracy and speed of the detection process can potentially have a significant impact on population health via early diagnosis and intervention. Motivated by this, we propose a recognition pipeline based on deep convolutional neural networks. In our pipeline, we design lightweight networks called SI2DRNet-vl along with six methods to further boost the detection performance. Without any fine-tuning, our recognition pipeline outperforms state of the art on the Messidor dataset along with 5.26x fewer in total parameters and 2.48x fewer in total floating operations.

Finding the locations and identities of faces in videos is a very important task in numerous applications. In this paper, we propose a correlation-based face detection approach to improve the performance of face recognition tasks for videos. We apply correlation measures to pairs of response maps which are generated from automatically selected neurons in deep convolutional neural network (CNN) models to detect faces in each video frame. The embeddings extracted from faces cropped by our proposed approach are more consistent across each video sequence and more suitable for face recognition and clustering tasks. Experimental results from the YouTube Faces (YTF) dataset demonstrate that our proposed approach is more robust and achieves better recognition accuracy compared to state-of-the-art face detection approaches.

In this paper, we propose Confidence Network (ConfNet) which not only makes predictions on input images but also generates a confidence score that estimates the probability of correctness of each prediction. Furthermore, Confidence Loss is proposed to make ConfNet automatically learn confidence scores in the training phase. The experiments on two public datasets show that the confidence scores generated by ConfNet are highly correlated with the model accuracy and outperforms two related methods. When stacking two ConfNets in a cascade structure, 3.8x computational cost can be saved compared to the single state-of-the-art model with only 0.1 % increase of error rate.

We study a class of non-parametric density estimators under Bayesian settings. The estimators are obtained by adaptively partitioning the sample space. Under a suitable prior, we analyze the concentration rate of the posterior distribution, and demonstrate that the rate does not directly depend on the dimension of the problem in several special cases. Another advantage of this class of Bayesian density estimators is that it can adapt to the unknown smoothness of the true density function, thus achieving the optimal convergence rate without artificial conditions on the density. We also validate the theoretical results on a variety of simulated data sets.

Mass cytometry (CyTOF) has greatly expanded the capability of cytometry. It is now easy to generate multiple CyTOF samples in a single study, with each sample containing single-cell measurement on 50 markers for more than hundreds of thousands of cells. Current methods do not adequately address the issues concerning combining multiple samples for subpopulation discovery, and these issues can be quickly and dramatically amplified with increasing number of samples. To overcome this limitation, we developed Partition-Assisted Clustering and Multiple Alignments of Networks (PAC-MAN) for the fast automatic identification of cell populations in CyTOF data closely matching that of expert manual-discovery, and for alignments between subpopulations across samples to define dataset-level cellular states. PAC-MAN is computationally efficient, allowing the management of very large CyTOF datasets, which are increasingly common in clinical studies and cancer studies that monitor various tissue samples for each subject.

Given $iid$ observations from an unknown continuous distribution defined on some domain $\Omega$, we propose a nonparametric method to learn a piecewise constant function to approximate the underlying probability density function. Our density estimate is a piecewise constant function defined on a binary partition of $\Omega$. The key ingredient of the algorithm is to use discrepancy, a concept originates from Quasi Monte Carlo analysis, to control the partition process. The resulting algorithm is simple, efficient, and has provable convergence rate. We demonstrate empirically its efficiency as a density estimation method. We also show how it can be utilized to find good initializations for k-means.

MOTIVATION: Next-generation sequence analysis has become an important task both in laboratory and clinical settings. A key stage in the majority sequence analysis workflows, such as resequencing, is the alignment of genomic reads to a reference genome. The accurate alignment of reads with large indels is a computationally challenging task for researchers. RESULTS: We introduce SeqAlto as a new algorithm for read alignment. For reads longer than or equal to 100 bp, SeqAlto is up to 10 × faster than existing algorithms, while retaining high accuracy and the ability to align reads with large (up to 50 bp) indels. This improvement in efficiency is particularly important in the analysis of future sequencing data where the number of reads approaches many billions. Furthermore, SeqAlto uses less than 8 GB of memory to align against the human genome. SeqAlto is benchmarked against several existing tools with both real and simulated data. AVAILABILITY: Linux and Mac OS X binaries free for academic use are available at http://www.stanford.edu/group/wonglab/seqalto CONTACT: [email protected].

SUMMARY: We present an open source, platform independent tool, called CisGenome Browser, which can work together with any other data analysis program to serve as a flexible component for genomic data visualization. It can also work by itself as a standalone genome browser. By working as a light-weight web server, CisGenome Browser is a convenient tool for data sharing between labs. It has features that are specifically designed for ultra high-throughput sequencing data visualization. AVAILABILITY: http://biogibbs.stanford.edu/ approximately jiangh/browser/

MOTIVATION: Splice junction microarrays and RNA-seq are two popular ways of quantifying splice variants within a cell. Unfortunately, isoform expressions cannot always be determined from the expressions of individual exons and splice junctions. While this issue has been noted before, the extent of the problem on various platforms has not yet been explored, nor have potential remedies been presented. RESULTS: We propose criteria that will guarantee identifiability of an isoform deconvolution model on exon and splice junction arrays and in RNA-Seq. We show that up to 97% of 2256 alternatively spliced human genes selected from the RefSeq database lead to identifiable gene models in RNA-seq, with similar results in mouse. However, in the Human Exon array only 26% of these genes lead to identifiable models, and even in the most comprehensive splice junction array only 69% lead to identifiable models. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: The development of RNA sequencing (RNA-Seq) makes it possible for us to measure transcription at an unprecedented precision and throughput. However, challenges remain in understanding the source and distribution of the reads, modeling the transcript abundance and developing efficient computational methods. In this article, we develop a method to deal with the isoform expression estimation problem. The count of reads falling into a locus on the genome annotated with multiple isoforms is modeled as a Poisson variable. The expression of each individual isoform is estimated by solving a convex optimization problem and statistical inferences about the parameters are obtained from the posterior distribution by importance sampling. Our results show that isoform expression inference in RNA-Seq is possible by employing appropriate statistical methods.

The differentiation of embryonic stem cells is initiated by a gradual loss of pluripotency-associated transcripts and induction of differentiation genes. Accordingly, the detection of differentially expressed genes at the early stages of differentiation could assist the identification of the causal genes that either promote or inhibit differentiation. The previous methods of identifying differentially expressed genes by comparing different cell types would inevitably include a large portion of genes that respond to, rather than regulate, the differentiation process. We demonstrate through the use of biological replicates and a novel statistical approach that the gene expression data obtained without prior separation of cell types are informative for detecting differentially expressed genes at the early stages of differentiation. Applying the proposed method to analyze the differentiation of murine embryonic stem cells, we identified and then experimentally verified Smarcad1 as a novel regulator of pluripotency and self-renewal. We formalized this statistical approach as a statistical test that is generally applicable to analyze other differentiation processes.

Learning the structure of Bayesian networks(BNs) is known to be NP-complete and most of the recent work in the field is based on heuristics. Many recent approaches to the problem trade correctness and exactness for faster computation and are still computationally infeasible, except for networks with few variables. In this paper we present a software/hardware co-design approach to learning Bayesian networks from experimental data that is scalable to very large networks. Our implementation improves the performance of algorithms that are traditionally developed based on the Von Neumann computing paradigm by more than four orders of magnitude. Through parallel implementation and exploitation of the reconfigurability of Field Programmable Gate Array (FPGA) systems our design enables scientists to apply BN learning techniques to large problems such as studies in molecular biology where the number of variables in the system overwhelms any state of the art software implementations. We describe how we combine Markov Chain Monte Carlo (MCMC) sampling with Bayesian network learning techniques as well as supervised learning methods in a parallel and scalable design. We also present how our design is mapped and customized to run on the Berkeley Emulation Engine 2 (BEE2) multi-FPGA system. Experimental results are presented on synthetic data sets generated from standard Bayesian networks as well as a real life problem in the context of systems biology

SeqMap is a tool for mapping large amount of short sequences to the genome. It is designed for finding all the places in a reference genome where each sequence may come from. This task is essential to the analysis of data from ultra high-throughput sequencing machines. With a carefully designed index-filtering algorithm and an efficient implementation, SeqMap can map tens of millions of short sequences to a genome of several billions of nucleotides. Multiple substitutions and insertions/deletions of the nucleotide bases in the sequences can be tolerated and therefore detected. SeqMap supports FASTA input format and various output formats, and provides command line options for tuning almost every aspect of the mapping process. A typical mapping can be done in a few hours on a desktop PC. Parallel use of SeqMap on a cluster is also very straightforward.

MOTIVATION: Microarray designs have become increasingly probe-rich, enabling targeting of specific features, such as individual exons or single nucleotide polymorphisms. These arrays have the potential to achieve quantitative high-throughput estimates of transcript abundances, but currently these estimates are affected by biases due to cross-hybridization, in which probes hybridize to off-target transcripts. RESULTS: To study cross-hybridization, we map Affymetrix exon array probes to a set of annotated mRNA transcripts, allowing a small number of mismatches or insertion/deletions between the two sequences. Based on a systematic study of the degree to which probes with a given match type to a transcript are affected by cross-hybridization, we developed a strategy to correct for cross-hybridization biases of gene-level expression estimates. Comparison with Solexa ultra high-throughput sequencing data demonstrates that correction for cross-hybridization leads to a significant improvement of gene expression estimates. AVAILABILITY: We provide mappings between human and mouse exon array probes and off-target transcripts and provide software extending the GeneBASE program for generating gene-level expression estimates including the cross-hybridization correction http://biogibbs.stanford.edu/~kkapur/GeneBase/.

In the subsection ''Initial probabilities'' of the Results section, the first sentence was incorrect and should say: These probabilities, denoted by P 0 (RET) and P 0 (LOSS) 1 P 0 (RET), specify the probabilities of RET and LOSS for the pterminal marker on a chromosome.

BACKGROUND: Many statistical algorithms combine microarray expression data and genome sequence data to identify transcription factor binding motifs in the low eukaryotic genomes. Finding cis-regulatory elements in higher eukaryote genomes, however, remains a challenge, as searching in the promoter regions of genes with similar expression patterns often fails. The difficulty is partially attributable to the poor performance of the similarity measures for comparing expression profiles. The widely accepted measures are inadequate for distinguishing genes transcribed from distinct regulatory mechanisms in the complicated genomes of higher eukaryotes. RESULTS: By defining the regulatory similarity between a gene pair as the number of common known transcription factor binding motifs in the promoter regions, we compared the performance of several expression distance measures on seven mouse expression data sets. We propose a new distance measure that accounts for both the linear trends and fold-changes of expression across the samples. CONCLUSION: The study reveals that the proposed distance measure for comparing expression profiles enables us to identify genes with large number of common regulatory elements because it reflects the inherent regulatory information better than widely accepted distance measures such as the Pearson's correlation or cosine correlation with or without log transformation.

BACKGROUND: Like microarray-based investigations, high-throughput proteomics techniques require machine learning algorithms to identify biomarkers that are informative for biological classification problems. Feature selection and classification algorithms need to be robust to noise and outliers in the data. RESULTS: We developed a recursive support vector machine (R-SVM) algorithm to select important genes/biomarkers for the classification of noisy data. We compared its performance to a similar, state-of-the-art method (SVM recursive feature elimination or SVM-RFE), paying special attention to the ability of recovering the true informative genes/biomarkers and the robustness to outliers in the data. Simulation experiments show that a 5%- approximately 20% improvement over SVM-RFE can be achieved regard to these properties. The SVM-based methods are also compared with a conventional univariate method and their respective strengths and weaknesses are discussed. R-SVM was applied to two sets of SELDI-TOF-MS proteomics data, one from a human breast cancer study and the other from a study on rat liver cirrhosis. Important biomarkers found by the algorithm were validated by follow-up biological experiments. CONCLUSION: The proposed R-SVM method is suitable for analyzing noisy high-throughput proteomics and microarray data and it outperforms SVM-RFE in the robustness to noise and in the ability to recover informative features. The multivariate SVM-based method outperforms the univariate method in the classification performance, but univariate methods can reveal more of the differentially expressed features especially when there are correlations between the features.

Loss of heterozygosity (LOH) of chromosomal regions bearing tumor suppressors is a key event in the evolution of epithelial and mesenchymal tumors. Identification of these regions usually relies on genotyping tumor and counterpart normal DNA and noting regions where heterozygous alleles in the normal DNA become homozygous in the tumor. However, paired normal samples for tumors and cell lines are often not available. With the advent of oligonucleotide arrays that simultaneously assay thousands of single-nucleotide polymorphism (SNP) markers, genotyping can now be done at high enough resolution to allow identification of LOH events by the absence of heterozygous loci, without comparison to normal controls. Here we describe a hidden Markov model-based method to identify LOH from unpaired tumor samples, taking into account SNP intermarker distances, SNP-specific heterozygosity rates, and the haplotype structure of the human genome. When we applied the method to data genotyped on 100 K arrays, we correctly identified 99% of SNP markers as either retention or loss. We also correctly identified 81% of the regions of LOH, including 98% of regions greater than 3 megabases. By integrating copy number analysis into the method, we were able to distinguish LOH from allelic imbalance. Application of this method to data from a set of prostate samples without paired normals identified known regions of prevalent LOH. We have developed a method for analyzing high-density oligonucleotide SNP array data to accurately identify of regions of LOH and retention in tumors without the need for paired normal samples.

Summary One central problem in science and engineering is predicting unseen outcome via relevant knowledge gained from data, where accuracy of generalization is the key. In the context of classification, we argue that higher generalization accuracy is achievable via ψ-learning, when a certain class of non-convex rather than convex cost functions are employed. To deliver attainable higher generalization accuracy, we propose two computational strategies via a global optimization technique–difference convex programming, which relies on a decomposition of the cost function into a difference of two convex functions. The first strategy solves sequential quadratic programs. The second strategy, combining this with the method of Branch-and-Bound, is more computationally intensive but is capable of producing global optima. Numerical experiments suggest that the algorithms realize the desired generalization ability of ψ-learning.

Motivation: Building an accurate binding model for a transcription factor (TF) is essential to differentiate its true binding targets from those spurious ones. This is an important step toward understanding gene regulation. Results: This paper describes a boosting approach to modeling TF–DNA binding. Different from the widely used weight matrix model, which predicts TF–DNA binding based on a linear combination of position-specific contributions, our approach builds a TF binding classifier by combining a set of weight matrix based classifiers, thus yielding a non-linear binding decision rule. The proposed approach was applied to the ChIP-chip data of Saccharomyces cerevisiae. When compared with the weight matrix method, our new approach showed significant improvements on the specificity in a majority of cases. Contact: [email protected] Supplementary information: The software and the Supplementary data are available at http://biogibbs.stanford.edu/~hong2004/MotifBooster/.

MOTIVATION: Tiling array is a new type of microarray that can be used to survey genomic transcriptional activities and transcription factor binding sites at high resolution. The goal of this paper is to develop effective statistical tools to identify genomic loci that show transcriptional or protein binding patterns of interest. RESULTS: A two-step approach is proposed and is implemented in TileMap. In the first step, a test-statistic is computed for each probe based on a hierarchical empirical Bayes model. In the second step, the test-statistics of probes within a genomic region are used to infer whether the region is of interest or not. Hierarchical empirical Bayes model shrinks variance estimates and increases sensitivity of the analysis. It allows complex multiple sample comparisons that are essential for the study of temporal and spatial patterns of hybridization across different experimental conditions. Neighboring probes are combined through a moving average method (MA) or a hidden Markov model (HMM). Unbalanced mixture subtraction is proposed to provide approximate estimates of false discovery rate for MA and model parameters for HMM. AVAILABILITY: TileMap is freely available at http://biogibbs.stanford.edu/~jihk/TileMap/index.htm. SUPPLEMENTARY INFORMATION: http://biogibbs.stanford.edu/~jihk/TileMap/index.htm (includes coloured versions of all figures).

BACKGROUND: Collecting and managing information is a challenging task in a genome-wide profiling research project. Most databases and online computational tools require a direct human involvement. Information and computational results are presented in various multimedia formats (e.g., text, image, PDF, word files, etc.), many of which cannot be automatically processed by computers in biologically meaningful ways. In addition, the quality of computational results is far from perfect and requires nontrivial manual examination. The timely selection, integration and interpretation of heterogeneous biological information still heavily rely on the sensibility of biologists. Biologists often feel overwhelmed by the huge amount of and the great diversity of distributed heterogeneous biological information. DESCRIPTION: We developed an information management application called GeneNotes. GeneNotes is the first application that allows users to collect and manage multimedia biological information about genes/ESTs. GeneNotes provides an integrated environment for users to surf the Internet, collect notes for genes/ESTs, and retrieve notes. GeneNotes is supported by a server that integrates gene annotations from many major databases (e.g., HGNC, MGI, etc.). GeneNotes uses the integrated gene annotations to (a) identify genes given various types of gene IDs (e.g., RefSeq ID, GenBank ID, etc.), and (b) provide quick views of genes. GeneNotes is free for academic usage. The program and the tutorials are available at: http://bayes.fas.harvard.edu/genenotes/. CONCLUSIONS: GeneNotes provides a novel human-computer interface to assist researchers to collect and manage biological information. It also provides a platform for studying how users behave when they manipulate biological information. The results of such study can lead to innovation of more intelligent human-computer interfaces that greatly shorten the cycle of biology research.

The Ubiquitous Bio-Information Computing (UBIC2) project aims to disseminate protocols and software packages to facilitate the development of heterogeneous bio-information computing units that are interoperable and may run distributedly. UBIC2 specifies biological data in XML formats and queries data using XQuery. The UBIC2 programming library provides interfaces for integrating, retrieving, and manipulating heterogeneous biological data. Interoperability is achieved via Simple Object Access Protocol (SOAP) based web services. The documents and software packages of UBIC2 are available at .

Biological information computing is rapidly advancing from homogeneous data computation to large-scale heterogeneous data computation. However, the development of data specification protocols, software middleware, and Web services, which support large-scale heterogeneous data exchange, integration, and computation, generally falls behind data expansion rates and bioinformatics demands. The ubiquitous bio-information computing (UBlC/sup 2/) project aims to disseminate software packages to assist the development of heterogeneous bio-information computing applications that are interoperable and may run distributedly. UBlC/sup 2/ lays down the software architecture for integrating, retrieving, and manipulating heterogeneous biological information so that data behave like being stored in a unified database, UBIC/sup 2/ programming library implements the software architecture and provides application programming interfaces (APIs) to facilitate the development of heterogeneous bio-information computing applications. To achieve interoperability, UBIC/sup 2/ Web services use XML-based data communication means, which allow distributed applications to consume heterogeneous bio-information regardless of platforms. The documents and software package of UBlC/sup 2/ are available at http://www.ubic2.org.

We describe a computational approach to predict transcription factors that interact with a given transcription factor, or a given family of transcription factors. We first collect a set of upstream sequences, to which a particular transcription factor or a family of transcription factors may bind. This set of upstream sequences is regarded as our training set. We collect a set of a large number of randomly chosen upstream sequences as the control set. We define a random variable to represent the clustering information of any putative transcription factor binding sites (TFBSs) in the control set. We calibrate the observed clusters of TFBSs in the training set to the distribution of the random variable representing the clustering information in the control set. We select the significant clusters from the training set and report the putative transcription factors that can bind to the TFBSs in these clusters. These reported transcription factors are candidates of interactive partners of the transcription factor (family) we started from. We applied this approach to discover transcription factors that may cooperate with E2F family proteins. We have identified 15 candidate interactive partners of E2F. Among them, 5 have been suggested or verified by previous biological studies.

MOTIVATION: Oligonucleotide microarrays allow genotyping of thousands of single-nucleotide polymorphisms (SNPs) in parallel. Recently, this technology has been applied to loss-of-heterozygosity (LOH) analysis of paired normal and tumor samples. However, methods and software for analyzing such data are not fully developed. RESULT: Here, we report automated methods for pooling SNP array replicates to make LOH calls, visualizing SNP and LOH data along chromosomes in the context of genes and cytobands, making statistical inference to identify shared LOH regions, clustering samples based on LOH profiles and correlating the clustering results to clinical variables. Application of these methods to prostate and breast cancer datasets generates biologically important results. AVAILABILITY: The software module dChipSNP implementing these methods is available at http://biosun1.harvard.edu/complab/dchip/snp/ SUPPLEMENTARY INFORMATION: The breast cancer data are provided by Andrea L. Richardson, Zhigang C. Wang and James D. Iglehart.

Simulated annealing has been one of the most popular stochastic optimization methods used in the VLSI CAD eld in the past tw odecades.Recently, a new Monte Carlo and optimization method, named dynamic weighting Monte Carlo [WL97], has been introduced and successfully applied to the traveling salesman problem, neural net w orktraining [WL97], and spin-glasses simulation [LW99].In this paper, we h a v e successfully applied dynamic w eighting Monte Carlo algorithm to the constrained oorplan design with consideration of both area and wirelength minimization.Our application scenario is the constrained oorplan design for mixed signal MCMs, where w eneed to place all the analog modules together in groups so that they can share common pow er and ground planes, which are separate from those used b y the digital modules.Our experiments indicate that the dynamic weighting Monte Carlo algorithm is very effectiv e for constrained oorplan optimization.It outperforms the simulated annealing for a real mixed signal MCM design b y 19:5% in wirelength, with sligh t area improvement.This is the rst work adopting the dynamic weighting Monte Carlo optimization method for solving VLSI CAD problems.We believe that this method has applications to many other VLSI CAD optimization problems.

In the past two decades, the simulated annealing technique has been considered as a powerful approach to handle many NP-hard optimization problems in VLSI designs. Recently, a new Monte Carlo and optimization technique, named simulated tempering, was invented and has been successfully applied to many scientific problems, from random field Ising modeling to the traveling salesman problem. It is designed to overcome the drawback in simulated annealing when the problem has a rough energy landscape with many local minima separated by high energy barriers. In this paper, we have successfully applied a version of relaxed simulated tempering to slicing floorplan design with consideration of both area and wirelength optimization. Good experimental results were obtained.

Block sizes of practical vector quantization (VQ) image coders are not large enough to exploit all high-order statistical dependencies among pixels. Therefore, adaptive entropy coding of VQ indexes via statistical context modeling can significantly reduce the bit rate of VQ coders for given distortion. Address VQ was a pioneer work in this direction. In this paper we develop a framework of conditional entropy coding of VQ indexes (CECOVI) based on a simple Bayesian-type method of estimating probabilities conditioned on causal contexts, CECOVI is conceptually cleaner and algorithmically more efficient than address VQ, with address-VQ technique being its special case. It reduces the bit rate of address VQ by more than 20% for the same distortion, and does so at only a tiny fraction of address VQ's computational cost.

Vector quantization (VQ) is a source coding methodology with provable rate-distortion optimality. However, despite more than two decades of intensive research, VQ theoretical promise is yet to be fully realized in image compression practice. Restricted by high VQ complexity in dimensions and due to high-order sample correlations in images, block sizes of practical VQ image coders are hardly large enough to achieve the rate-distortion optimality. Among the large number of VQ variants in the literature, a technique called address VQ (A-VQ) by Nasrabadi and Feng (1990) achieved the best rate-distortion performance so far to the best of our knowledge. The essence of A-VQ is to effectively increase VQ dimensions by a lossless coding of a group of 16-dimensional VQ codewords that are spatially adjacent. From a different perspective, we can consider a signal source that is coded by memoryless basic VQ to be just another signal source whose samples are the indices of the memoryless VQ codewords, and then induce the problem of lossless compression of the VQ-coded source. If the memoryless VQ is not rate-distortion optimal (often the case in practice), then there must exist hidden structures between the samples of VQ-coded source (VQ codewords). Therefore, an alternative way of approaching the rate-distortion optimality is to model and utilize these inter-codewords structures or correlations by context modeling and conditional entropy coding of VQ indexes.

Reports on a new method in which spatially correlated magnetic resonance (MR) or X-ray computed tomography (CT) images are employed as a source of prior information in the Bayesian reconstruction of positron emission tomography (PET) images. This new method incorporates the correlated structural images as anatomic templates which can be used for extracting information about boundaries that separate regions exhibiting different tissue characteristics. In order to avoid the possible introduction of artifacts caused by discrepancies between functional and anatomic boundaries, the authors propose a new method called the "weighted line site" method, in which a prior structural image is employed in a modified updating scheme for the boundary variable used in the iterative Bayesian reconstruction. This modified scheme is based on the joint probability of structural and functional boundaries. As to the structural information provided by CT or MR images, only those which have high joint probability with the corresponding PET data are used; whereas other boundary information that is not supported by the PET image is suppressed. The new method has been validated by computer simulation and phantom studies. The results of these validation studies indicate that this new method offers significant improvements in image quality when compared to other reconstruction algorithms, including the filtered backprojection method and the maximum likelihood approach, as well as the Bayesian method without the use of the prior boundary information.

The authors propose a Bayesian model for the restoration of images based on counts of emitted photons. The model treats blurring within the context of an incomplete data problem and utilizes a Gibbs prior to model the spatial correlation of neighboring regions. The Gibbs prior includes line sites to account for boundaries between regions, and the line sites are assigned continuous values to permit efficient estimation using a method called iterative conditional averages. In addition, the effect of blurring in masking differences between images and the effects of misspecifying the amount of blurring are discussed.>