Adaptive processing techniques based on hidden Markov models for characterizing very small channel currents buried in noise and deterministic interferences.

Techniques for characterizing very small single-channel currents buried in background noise are described and tested on simulated data to give confidence when applied to real data. Single channel currents are represented as a discrete-time, finite-state, homogeneous, Markov process, and the noise that obscures the signal is assumed to be white and Gaussian. The various signal model parameters, such as the Markov state levels and transition probabilities, are unknown. In addition to white Gaussian noise, the signal can be corrupted by deterministic interferences of known form but unknown parameters, such as the sinusoidal disturbance stemming from AC interference and a drift of the base line owing to a slow development of liquid-junction potentials. To characterize the signal buried in such stochastic and deterministic interferences, the problem is first formulated in the framework of a Hidden Markov Model and then the Expectation Maximization algorithm is applied to obtain the maximum likelihood estimates of the model parameters (state levels, transition probabilities), signals, and the parameters of the deterministic disturbances. Using fictitious channel currents embedded in the idealized noise, we first show that the signal processing technique is capable of characterizing the signal characteristics quite accurately even when the amplitude of currents is as small as 5-10 fA. The statistics of the signal estimated from the processing technique include the amplitude, mean open and closed duration, open-time and closed-time histograms, probability of dwell-time and the transition probability matrix. With a periodic interference composed, for example, of 50 Hz and 100 Hz components, or a linear drift of the baseline added to the segment containing channel currents and white noise, the parameters of the deterministic interference, such as the amplitude and phase of the sinusoidal wave, or the rate of linear drift, as well as all the relevant statistics of the signal, are accurately estimated with the algorithm we propose. Also, if the frequencies of the periodic interference are unknown, they can be accurately estimated. Finally, we provide a technique by which channel currents originating from the sum of two or more independent single channels are decomposed so that each process can be separately characterized. This process is also formulated as a Hidden Markov Model problem and solved by applying the Expectation Maximization algorithm. The scheme relies on the fact that the transition matrix of the summed Markov process can be construed as a tensor product of the transition matrices of individual processes.     

Classification of HIV-1 sequences using profile Hidden Markov Models

Accurate classification of HIV-1 subtypes is essential for studying the dynamic spatial distribution pattern of HIV-1 subtypes and also for developing effective methods of treatment that can be targeted to attack specific subtypes. We propose a classification method based on profile Hidden Markov Model that can accurately identify an unknown strain. We show that a standard method that relies on the construction of a positive training set only, to capture unique features associated with a particular subtype, can accurately classify sequences belonging to all subtypes except B and D. We point out the drawbacks of the standard method; namely, an arbitrary choice of threshold to distinguish between true positives and true negatives, and the inability to discriminate between closely related subtypes. We then propose an improved classification method based on construction of a positive as well as a negative training set to improve discriminating ability between closely related subtypes like B and D. Finally, we show how the improved method can be used to accurately determine the subtype composition of Common Recombinant Forms of the virus that are made up of two or more subtypes. Our method provides a simple and highly accurate alternative to other classification methods and will be useful in accurately annotating newly sequenced HIV-1 strains.     

Hidden Markov modeling for single channel kinetics with filtering and correlated noise

Hidden Markov modeling (HMM) can be applied to extract single channel kinetics at signal-to-noise ratios that are too low for conventional analysis. There are two general HMM approaches: traditional Baum's reestimation and direct optimization. The optimization approach has the advantage that it optimizes the rate constants directly. This allows setting constraints on the rate constants, fitting multiple data sets across different experimental conditions, and handling nonstationary channels where the starting probability of the channel depends on the unknown kinetics. We present here an extension of this approach that addresses the additional issues of low-pass filtering and correlated noise. The filtering is modeled using a finite impulse response (FIR) filter applied to the underlying signal, and the noise correlation is accounted for using an autoregressive (AR) process. In addition to correlated background noise, the algorithm allows for excess open channel noise that can be white or correlated. To maximize the efficiency of the algorithm, we derive the analytical derivatives of the likelihood function with respect to all unknown model parameters. The search of the likelihood space is performed using a variable metric method. Extension of the algorithm to data containing multiple channels is described. Examples are presented that demonstrate the applicability and effectiveness of the algorithm. Practical issues such as the selection of appropriate noise AR orders are also discussed through examples.     

Predicting protein subcellular location using digital signal processing

The biological functions of a protein are closely related to its attributes in a cell. With the rapid accumulation of newly found protein sequence data in databanks, it is highly desirable to develop an automated method for predicting the subcellular location of proteins. The establishment of such a predictor will expedite the functional determination of newly found proteins and the process of prioritizing genes and proteins identified by genomic efforts as potential molecular targets for drug design. The traditional algorithms for predicting these attributes were based solely on amino acid composition in which no sequence order effect was taken into account. To improve the prediction quality, it is necessary to incorporate such an effect. However, the number of possible patterns in protein sequences is extremely large, posing a formidable difficulty for realizing this goal. To deal with such difficulty, a well-developed tool in digital signal processing named digital Fourier transform (DFT) [1] was introduced. After being translated to a digital signal according to the hydrophobicity of each amino acid, a protein was analyzed by DFT within the frequency domain. A set of frequency spectrum parameters, thus obtained, were regarded as the factors to represent the sequence order effect. A significant improvement in prediction quality was observed by incorporating the frequency spectrum parameters with the conventional amino acid composition. One of the crucial merits of this approach is that many existing tools in mathematics and engineering can be easily applied in the predicting process. It is anticipated that digital signal processing may serve as a useful vehicle for many other protein science areas.     

Hidden Markov analysis of mechanosensitive ion channel gating

Patch clamp data from the large conductance mechanosensitive channel (MscL) in E. coli was studied with the aim of developing a strategy for statistical analysis based on hidden Markov models (HMMs) and determining the number of conductance levels of the channel, together with mean current, mean dwell time and equilibrium probability of occupancy for each level. The models incorporated state-dependent white noise and moving average adjustment for filtering, with maximum likelihood parameter estimates obtained using an EM (expectation-maximisation) based iteration. Adjustment for filtering was included as it could be expected that the electronic filter used in recording would have a major effect on obviously brief intermediate conductance level sojourns. Preliminary data analysis revealed that the brevity of intermediate level sojourns caused difficulties in assignment of data points to levels as a result of over-estimation of noise variances. When reasonable constraints were placed on these variances using the better determined noise variances for the closed and fully open levels, idealisation anomalies were eliminated. Nevertheless, simulations suggested that mean sojourn times for the intermediate levels were still considerably over-estimated, and that recording bandwidth was a major limitation; improved results were obtained with higher bandwidth data (10 kHz sampled at 25 kHz). The simplest model consistent with these data had four open conductance levels, intermediate levels being approximately 20%, 51% and 74% of fully open. The mean lifetime at the fully open level was about 1 ms; estimates for the three intermediate levels were 54-92 micros, probably still over-estimates.     

The effect of tetramethylammonium on single sodium channel currents.

Voltage-dependent Na conductance of rat myotubes was studied by patch recordings of single-channels. The patches were excised from the cell with the patch electrode, and the cytoplasmic surface was bathed in either CsF or tetramethylammonium (TMA)-F. Inward currents were examined from -20 to -50 mV. In this range Cs and TMA both appeared to be nearly impermeant, but TMA blocked the channel in a voltage-dependent manner. A first-order blocking site was located a maximum of 89% of the way through the membrane field from the cytoplasmic surface.     

Characterization of single channel currents from primary cilia of renal epithelial cells

The primary cilium is a ubiquitous, non-motile microtubular organelle lacking the central pair of microtubules found in motile cilia. Primary cilia are surrounded by a membrane, which has a unique complement of membrane proteins, and may thus be functionally different from the plasma membrane. The function of the primary cilium remains largely unknown. However, primary cilia have important sensory transducer properties, including the response of renal epithelial cells to fluid flow or mechanical stimulation. Recently, renal cystic diseases have been associated with dysfunctional ciliary proteins. Although the sensory properties of renal epithelial primary cilia may be associated with functional channel activity in the organelle, information in this regard is still lacking. This may be related to the inherent difficulties in assessing electrical activity in this rather small and narrow organelle. In the present study, we provide the first direct electrophysiological evidence for the presence of single channel currents from isolated primary cilia of LLC-PK1 renal epithelial cells. Several channel phenotypes were observed, and addition of vasopressin increased cation channel activity, which suggests the regulation, by the cAMP pathway of ciliary conductance. Ion channel reconstitution of ciliary versus plasma membranes indicated a much higher channel density in cilia. At least three channel proteins, polycystin-2, TRPC1, and interestingly, the alpha-epithelial sodium channel, were immunodetected in this organelle. Ion channel activity in the primary cilium of renal cells may be an important component of its role as a sensory transducer.     

Recent applications of Hidden Markov Models in computational biology

This paper examines recent developments and applications of Hidden Markov Models (HMMs) to various problems in computational biology, including multiple sequence alignment, homology detection, protein sequences classification, and genomic annotation.     

MicroRNA target prediction based on second-order Hidden Markov Model

MicroRNAs are one class of small single-stranded RNA of about 22 nt serving as important negative gene regulators. In animals, miRNAs mainly repress protein translation by binding itself to the 3′ UTR regions of mRNAs with imperfect complementary pairing. Although bioinformatics investigations have resulted in a number of target prediction tools, all of these have a common shortcoming—a high false positive rate. Therefore, it is important to further filter the predicted targets. In this paper, based on miRNA:target duplex, we construct a second-order Hidden Markov Model, implement Baum-Welch training algorithm and apply this model to further process predicted targets. The model trains the classifier by 244 positive and 49 negative miRNA:target interaction pairs and achieves a sensitivity of 72.54%, specificity of 55.10% and accuracy of 69.62% by 10-fold cross-validation experiments. In order to further verify the applicability of the algorithm, previously collected datasets, including 195 positive and 38 negative, are chosen to test it, with consistent results. We believe that our method will provide some guidance for experimental biologists, especially in choosing miRNA targets for validation.     

Restoration of single-channel currents using the segmental k-means method based on hidden Markov modeling

Patch-clamp recording provides an unprecedented means for study of detailed kinetics of ion channels at the single molecule level. Analysis of the recordings often begins with idealization of noisy recordings into continuous dwell-time sequences. Success of an analysis is contingent on accuracy of the idealization. I present here a statistical procedure based on hidden Markov modeling and k-means segmentation. The approach assumes a Markov scheme involving discrete conformational transitions for the kinetics of the channel and a white background noise for contamination of the observations. The idealization is sought to maximize a posteriori probability of the state sequence corresponding to the samples. The approach constitutes two fundamental steps. First, given a model, the Viterbi algorithm is applied to determine the most likely state sequence. With the resultant idealization, the model parameters are then empirically refined. The transition probabilities are calculated from the state sequences, and the current amplitudes and noise variances are determined from the ensemble means and variances of those samples belonging to the same conductance classes. The two steps are iterated until the likelihood is maximized. In practice, the algorithm converges rapidly, taking only a few iterations. Because the noise is taken into explicit account, it allows for a low signal/noise ratio, and consequently a relatively high bandwidth. The approach is applicable to data containing subconductance levels or multiple channels and permits state-dependent noises. Examples are given to elucidate its performance and practical applicability.     

Reducing noise in computed correlation functions using techniques from signal processing

Time correlation functions invariably suffer from random noise, especially at longer time intervals for which fewer data pairs are available. This noise is particularly of concern when calculating correlations that cannot be averaged over per-molecule contributions, such as stress in molecular simulations. In this work, a set of methods based in signal processing has been developed to reduce the inherent noise that is present in time- and frequency-domain representations of correlation functions. The stress time autocorrelation function, which leads to stress relaxation modulus and complex modulus, is used as an example. The difference between initial and final values of a time correlation function over a finite time domain is found to create so-called ‘leakage’ of noise from disallowed into harmonic frequencies during fast Fourier transformation. Decreasing this leakage effect through reflection to negative time and through applying a window function reduces noise levels significantly. Removing frequency components of insignificant magnitudes also provides significant noise reduction. Applying moving averages in the frequency and time domains also contributes to noise reduction. Specific results obtained by applying these methods to a model asphalt system enable more clear physical interpretations of the underlying relaxations after dramatic noise level reductions were attained.     

A sodium channel gating model based on single channel, macroscopic ionic, and gating currents in the squid giant axon.

Sodium channel gating behavior was modeled with Markovian models fitted to currents from the cut-open squid giant axon in the absence of divalent cations. Optimum models were selected with maximum likelihood criteria using single-channel data, then models were refined and extended by simultaneous fitting of macroscopic ionic currents, ON and OFF gating currents, and single-channel first latency densities over a wide voltage range. Best models have five closed states before channel opening, with inactivation from at least one closed state as well as the open state. Forward activation rate constants increase with depolarization, and deactivation rate constants increase with hyperpolarization. Rates of inactivation from the open or closed states are generally slower than activation or deactivation rates and show little or no voltage dependence. Channels tend to reopen several times before inactivating. Macroscopic rates of activation and inactivation result from a combination of closed, open and inactivated state transitions. At negative potentials the time to first opening dominates the macroscopic current due to slow activation rates compared with deactivation rates: channels tend to reopen rarely, and often inactivate from closed states before they reopen. At more positive potentials, the time to first opening and burst duration together produce the macroscopic current.     

A method for the prediction of GPCRs coupling specificity to G-proteins using refined profile Hidden Markov Models

Background  

G- Protein coupled receptors (GPCRs) comprise the largest group of eukaryotic cell surface receptors with great pharmacological interest. A broad range of native ligands interact and activate GPCRs, leading to signal transduction within cells. Most of these responses are mediated through the interaction of GPCRs with heterotrimeric GTP-binding proteins (G-proteins). Due to the information explosion in biological sequence databases, the development of software algorithms that could predict properties of GPCRs is important. Experimental data reported in the literature suggest that heterotrimeric G-proteins interact with parts of the activated receptor at the transmembrane helix-intracellular loop interface. Utilizing this information and membrane topology information, we have developed an intensive exploratory approach to generate a refined library of statistical models (Hidden Markov Models) that predict the coupling preference of GPCRs to heterotrimeric G-proteins. The method predicts the coupling preferences of GPCRs to G_s, G_i/o and G_q/11, but not G_12/13 subfamilies.     

Guanidine block of single channel currents activated by acetylcholine

The acetylcholine-activated channel of chick myotube was studied using the patch-clamp method. Single channel current amplitudes were measured between -300 and +250 mV in solutions containing the permeant ions Cs+ and guanidine (G+). G+ has a relative permeability, PG/PCs, of 1.6, but carries no more than half the current that Cs+ does, with an equivalent electrochemical driving force. Experiments using G+ revealed an asymmetry of the acetylcholine-activated channel, with G+ being more effective at reducing Cs+ currents when added to the outside than when added to the inside. The block caused by outside, but not inside, G+ was evident for both inward and outward currents. The block caused by outside G+ was voltage dependent, first increasing and then being partially relieved when the driving force was made more negative. Experiments with mixtures of Cs+ and G+ revealed anomalously low magnitudes for reversal potentials, relative to predictions based on the Goldman-Hodgkin-Katz equation. These findings are consistent with a two-well, three-barrier Eyring rate model for ion flow, and demonstrate that a highly permeant ion, guanidine, can block asymmetrically by acting from within the voltage field of the acetylcholine-activated channel.     

Models of retinal signal processing at high luminances

Summary In psychophysics the relation between the threshold luminance increment and the background luminance for visual increment detection, is known to become linear for high luminances. This so called Weber-law means that at high luminances the threshold is caused by the detection apparatus, and not by the quantum noise of the stimulus itself. A simple machine implementing the Weber-law is discussed. This machine obviates the need for an internal noise source (or dark light). It is the combined result of an apparatus that reduces the output event rate by causing the quantum to spike ratio to follow the input intensity, and a detection criterion that needs a constant number of extra output events to generate a positive response. The dynamic properties of the machine are described by the solutions of a simple though nonlinear differential equation. The supra threshold properties prove to mimic several of the responses known to occur at ganglion cell level in the cat's retina. A tentative model of an on-center receptive field is presented, and results obtained by simulating this model on a digital cumputer are compared with some recent electrophysiological findings. Finally a possible extension of the model to a full on-center/off-surround receptive field model is discussed.The authors are indebted to the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.) for financial support of a part of this investigation.We thank W. A. Aarnink for invaluable help in debugging and running the programs involved in this work.     

Profile Hidden Markov Models for the Detection of Viruses within Metagenomic Sequence Data

Rapid, sensitive, and specific virus detection is an important component of clinical diagnostics. Massively parallel sequencing enables new diagnostic opportunities that complement traditional serological and PCR based techniques. While massively parallel sequencing promises the benefits of being more comprehensive and less biased than traditional approaches, it presents new analytical challenges, especially with respect to detection of pathogen sequences in metagenomic contexts. To a first approximation, the initial detection of viruses can be achieved simply through alignment of sequence reads or assembled contigs to a reference database of pathogen genomes with tools such as BLAST. However, recognition of highly divergent viral sequences is problematic, and may be further complicated by the inherently high mutation rates of some viral types, especially RNA viruses. In these cases, increased sensitivity may be achieved by leveraging position-specific information during the alignment process. Here, we constructed HMMER3-compatible profile hidden Markov models (profile HMMs) from all the virally annotated proteins in RefSeq in an automated fashion using a custom-built bioinformatic pipeline. We then tested the ability of these viral profile HMMs (“vFams”) to accurately classify sequences as viral or non-viral. Cross-validation experiments with full-length gene sequences showed that the vFams were able to recall 91% of left-out viral test sequences without erroneously classifying any non-viral sequences into viral protein clusters. Thorough reanalysis of previously published metagenomic datasets with a set of the best-performing vFams showed that they were more sensitive than BLAST for detecting sequences originating from more distant relatives of known viruses. To facilitate the use of the vFams for rapid detection of remote viral homologs in metagenomic data, we provide two sets of vFams, comprising more than 4,000 vFams each, in the HMMER3 format. We also provide the software necessary to build custom profile HMMs or update the vFams as more viruses are discovered (http://derisilab.ucsf.edu/software/vFam).