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.     

Model-based fitting of single-channel dwell-time distributions

Single-channel recordings provide unprecedented resolutions on kinetics of conformational changes of ion channels. Several approaches exist for analysis of the data, including the dwell-time histogram fittings and the full maximal-likelihood approaches that fit either the idealized dwell-time sequence or more ambitiously the noisy data directly using hidden Markov modeling. Although the full maximum likelihood approaches are statistically advantageous, they can be time-consuming especially for large datasets and/or complex models. We present here an alternative approach for model-based fitting of one-dimensional and two-dimensional dwell-time histograms. To improve performance, we derived analytical expressions for the derivatives of one-dimensional and two-dimensional dwell-time distribution functions and employed the gradient-based variable metric method for fast search of optimal rate constants in a model. The algorithm also has the ability to allow for a first-order correction for the effects of missed events, global fitting across different experimental conditions, and imposition of typical constraints on rate constants including microscopic reversibility. Numerical examples are presented to illustrate the performance of the algorithm, and comparisons with the full maximum likelihood fitting are discussed.     

Stochastic Dynamic Model for Estimation of Rate Constants and Their Variances from Noisy and Heterogeneous PET Measurements

Tissue heterogeneity, radioactive decay and measurement noise are the main error sources in compartmental modeling used to estimate the physiologic rate constants of various radiopharmaceuticals from a dynamic PET study. We introduce a new approach to this problem by modeling the tissue heterogeneity with random rate constants in compartment models. In addition, the Poisson nature of the radioactive decay is included as a Poisson random variable in the measurement equations. The estimation problem will be carried out using the maximum likelihood estimation. With this approach, we do not only get accurate mean estimates for the rate constants, but also estimates for tissue heterogeneity within the region of interest and other possibly unknown model parameters, e.g. instrument noise variance, as well. We also avoid the problem of the optimal weighting of the data related to the conventionally used weighted least-squares method. The new approach was tested with simulated time–activity curves from the conventional three compartment – three rate constants model with normally distributed rate constants and with a noise mixture of Poisson and normally distributed random variables. Our simulation results showed that this new model gave accurate estimates for the mean of the rate constants, the measurement noise parameter and also for the tissue heterogeneity, i.e. for the variance of the rate constants within the region of interest.     

The power of two-dimensional dwell-time analysis for model discrimination, temporal resolution, multichannel analysis and level detection

Two-dimensional (2D) dwell-time analysis of time series of single-channel patch-clamp current was improved by employing a Hinkley detector for jump detection, introducing a genetic fit algorithm, replacing maximum likelihood by a least square criterion, averaging over a field of 9 or 25 bins in the 2D plane and normalizing per measuring time, not per events. Using simulated time series for the generation of the "theoretical" 2D histograms from assumed Markov models enabled the incorporation of the measured filter response and noise. The effects of these improvements were tested with respect to the temporal resolution, accuracy of the determination of the rate constants of the Markov model, sensitivity to noise and requirement of open time and length of the time series. The 2D fit was better than the classical hidden Markov model (HMM) fit in all tested fields. The temporal resolution of the two most efficient algorithms, the 2D fit and the subsequent HMM/beta fit, enabled the determination of rate constants 10 times faster than the corner frequency of the low-pass filter. The 2D fit was much less sensitive to noise. The requirement of computing time is a problem of the 2D fit (100 times that of the HMM fit) but can now be handled by personal computers. The studies revealed a fringe benefit of 2D analysis: it can reveal the "true" single-channel current when the filter has reduced the apparent current level by averaging over undetected fast gating.     

The Power of Two-Dimensional Dwell-Time Analysis for Model Discrimination, Temporal Resolution, Multichannel Analysis and Level Detection

Two-dimensional (2D) dwell-time analysis of time series of single-channel patch-clamp current was improved by employing a Hinkley detector for jump detection, introducing a genetic fit algorithm, replacing maximum likelihood by a least square criterion, averaging over a field of 9 or 25 bins in the 2D plane and normalizing per measuring time, not per events. Using simulated time series for the generation of the “theoretical” 2D histograms from assumed Markov models enabled the incorporation of the measured filter response and noise. The effects of these improvements were tested with respect to the temporal resolution, accuracy of the determination of the rate constants of the Markov model, sensitivity to noise and requirement of open time and length of the time series. The 2D fit was better than the classical hidden Markov model (HMM) fit in all tested fields. The temporal resolution of the two most efficient algorithms, the 2D fit and the subsequent HMM/beta fit, enabled the determination of rate constants 10 times faster than the corner frequency of the low-pass filter. The 2D fit was much less sensitive to noise. The requirement of computing time is a problem of the 2D fit (100 times that of the HMM fit) but can now be handled by personal computers. The studies revealed a fringe benefit of 2D analysis: it can reveal the “true” single-channel current when the filter has reduced the apparent current level by averaging over undetected fast gating.     

Estimating kinetic constants from single channel data.

The process underlying the opening and closing of ionic channels in biological or artificial lipid membranes can be modeled kinetically as a time-homogeneous Markov chain. The elements of the chain are kinetic states that can be either open or closed. A maximum likelihood procedure is described for estimating the transition rates between these states from single channel data. The method has been implemented for linear kinetic schemes of fewer than six states, and is suitable for nonstationary data in which one or more independent channels are functioning simultaneously. It also provides standard errors for all estimates of rate constants and permits testing of smoothly parameterized subhypotheses of a general model. We have illustrated our approach by analysis of single channel data simulated on a computer and have described a procedure for analysis of experimental data.     

Detection of recombination in DNA multiple alignments with hidden Markov models.

Conventional phylogenetic tree estimation methods assume that all sites in a DNA multiple alignment have the same evolutionary history. This assumption is violated in data sets from certain bacteria and viruses due to recombination, a process that leads to the creation of mosaic sequences from different strains and, if undetected, causes systematic errors in phylogenetic tree estimation. In the current work, a hidden Markov model (HMM) is employed to detect recombination events in multiple alignments of DNA sequences. The emission probabilities in a given state are determined by the branching order (topology) and the branch lengths of the respective phylogenetic tree, while the transition probabilities depend on the global recombination probability. The present study improves on an earlier heuristic parameter optimization scheme and shows how the branch lengths and the recombination probability can be optimized in a maximum likelihood sense by applying the expectation maximization (EM) algorithm. The novel algorithm is tested on a synthetic benchmark problem and is found to clearly outperform the earlier heuristic approach. The paper concludes with an application of this scheme to a DNA sequence alignment of the argF gene from four Neisseria strains, where a likely recombination event is clearly detected.     

Improved hidden Markov models for molecular motors, part 1: basic theory

Hidden Markov models (HMMs) provide an excellent analysis of recordings with very poor signal/noise ratio made from systems such as ion channels which switch among a few states. This method has also recently been used for modeling the kinetic rate constants of molecular motors, where the observable variable—the position—steadily accumulates as a result of the motor's reaction cycle. We present a new HMM implementation for obtaining the chemical-kinetic model of a molecular motor's reaction cycle called the variable-stepsize HMM in which the quantized position variable is represented by a large number of states of the Markov model. Unlike previous methods, the model allows for arbitrary distributions of step sizes, and allows these distributions to be estimated. The result is a robust algorithm that requires little or no user input for characterizing the stepping kinetics of molecular motors as recorded by optical techniques.     

Parameterization for In-Silico Modeling of Ion Channel Interactions with Drugs

Since the first Hodgkin and Huxley ion channel model was described in the 1950s, there has been an explosion in mathematical models to describe ion channel function. As experimental data has become richer, models have concomitantly been improved to better represent ion channel kinetic processes, although these improvements have generally resulted in more model complexity and an increase in the number of parameters necessary to populate the models. Models have also been developed to explicitly model drug interactions with ion channels. Recent models of drug-channel interactions account for the discrete kinetics of drug interaction with distinct ion channel state conformations, as it has become clear that such interactions underlie complex emergent kinetics such as use-dependent block. Here, we describe an approach for developing a model for ion channel drug interactions. The method describes the process of extracting rate constants from experimental electrophysiological function data to use as initial conditions for the model parameters. We then describe implementation of a parameter optimization method to refine the model rate constants describing ion channel drug kinetics. The algorithm takes advantage of readily available parallel computing tools to speed up the optimization. Finally, we describe some potential applications of the platform including the potential for gaining fundamental mechanistic insights into ion channel function and applications to in silico drug screening and development.     

Use of runs statistics for pattern recognition in genomic DNA sequences.

In this article, the use of the finite Markov chain imbedding (FMCI) technique to study patterns in DNA under a hidden Markov model (HMM) is introduced. With a vision of studying multiple runs-related statistics simultaneously under an HMM through the FMCI technique, this work establishes an investigation of a bivariate runs statistic under a binary HMM for DNA pattern recognition. An FMCI-based recursive algorithm is derived and implemented for the determination of the exact distribution of this bivariate runs statistic under an independent identically distributed (IID) framework, a Markov chain (MC) framework, and a binary HMM framework. With this algorithm, we have studied the distributions of the bivariate runs statistic under different binary HMM parameter sets; probabilistic profiles of runs are created and shown to be useful for trapping HMM maximum likelihood estimates (MLEs). This MLE-trapping scheme offers good initial estimates to jump-start the expectation-maximization (EM) algorithm in HMM parameter estimation and helps prevent the EM estimates from landing on a local maximum or a saddle point. Applications of the bivariate runs statistic and the probabilistic profiles in conjunction with binary HMMs for pattern recognition in genomic DNA sequences are illustrated via case studies on DNA bendability signals using human DNA data.     

Generalizing HMMs to Continuous Time for Fast Kinetics: Hidden Markov Jump Processes

The hidden Markov model (HMM) is a framework for time series analysis widely applied to single-molecule experiments. Although initially developed for applications outside the natural sciences, the HMM has traditionally been used to interpret signals generated by physical systems, such as single molecules, evolving in a discrete state space observed at discrete time levels dictated by the data acquisition rate. Within the HMM framework, transitions between states are modeled as occurring at the end of each data acquisition period and are described using transition probabilities. Yet, whereas measurements are often performed at discrete time levels in the natural sciences, physical systems evolve in continuous time according to transition rates. It then follows that the modeling assumptions underlying the HMM are justified if the transition rates of a physical process from state to state are small as compared to the data acquisition rate. In other words, HMMs apply to slow kinetics. The problem is, because the transition rates are unknown in principle, it is unclear, a priori, whether the HMM applies to a particular system. For this reason, we must generalize HMMs for physical systems, such as single molecules, because these switch between discrete states in “continuous time”. We do so by exploiting recent mathematical tools developed in the context of inferring Markov jump processes and propose the hidden Markov jump process. We explicitly show in what limit the hidden Markov jump process reduces to the HMM. Resolving the discrete time discrepancy of the HMM has clear implications: we no longer need to assume that processes, such as molecular events, must occur on timescales slower than data acquisition and can learn transition rates even if these are on the same timescale or otherwise exceed data acquisition rates.     

Estimating single-channel kinetic parameters from idealized patch-clamp data containing missed events.

We present here a maximal likelihood algorithm for estimating single-channel kinetic parameters from idealized patch-clamp data. The algorithm takes into account missed events caused by limited time resolution of the recording system. Assuming a fixed dead time, we derive an explicit expression for the corrected transition rate matrix by generalizing the theory of Roux and Sauve (1985, Biophys. J. 48:149-158) to the case of multiple conductance levels. We use a variable metric optimizer with analytical derivatives for rapidly maximizing the likelihood. The algorithm is applicable to data containing substates and multiple identical or nonidentical channels. It allows multiple data sets obtained under different experimental conditions, e.g., concentration, voltage, and force, to be fit simultaneously. It also permits a variety of constraints on rate constants and provides standard errors for all estimates of model parameters. The algorithm has been tested extensively on a variety of kinetic models with both simulated and experimental data. It is very efficient and robust; rate constants for a multistate model can often be extracted in a processing time of approximately 1 min, largely independent of the starting values.     

Estimation of kinetic rate constants from multi-channel recordings by a direct fit of the time series.

The maximum-likelihood technique for the direct estimation of rate constants from the measured patch clamp current is extended to the analysis of multi-channel recordings, including channels with subconductance levels. The algorithm utilizes a simplified approach for the calculation of the matrix exponentials of the probability matrix from the rate constants of the Markov model of the involved channel(s) by making use of the Kronecker sum and product. The extension to multi-channel analysis is tested by the application to simulated data. For these tests, three different channel models were selected: a two-state model, a three-state model with two open states of different conductance, and a three-state model with two closed states. For the simulations, time series of these models were calculated from the related first-order, finite-state, continuous-time Markov processes. Blue background noise was added, and the signals were filtered by a digital filter similar to the anti-aliasing low-pass. The tests showed that the fit algorithm revealed good estimates of the original rate constants from time series of simulated records with up to four independent and identical channels even in the case of signal-to-noise ratios being as low as 2. The number of channels in a record can be determined from the dependence of the likelihood on channel number. For large enough data sets, it takes on a maximum when the assumed channel number is equal to the "true" channel number.     

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.     

Sequence alignments and pair hidden Markov models using evolutionary history

This work presents a novel pairwise statistical alignment method based on an explicit evolutionary model of insertions and deletions (indels). Indel events of any length are possible according to a geometric distribution. The geometric distribution parameter, the indel rate, and the evolutionary time are all maximum likelihood estimated from the sequences being aligned. Probability calculations are done using a pair hidden Markov model (HMM) with transition probabilities calculated from the indel parameters. Equations for the transition probabilities make the pair HMM closely approximate the specified indel model. The method provides an optimal alignment, its likelihood, the likelihood of all possible alignments, and the reliability of individual alignment regions. Human alpha and beta-hemoglobin sequences are aligned, as an illustration of the potential utility of this pair HMM approach.     

Bayesian Estimation of the Active Concentration and Affinity Constants Using Surface Plasmon Resonance Technology

Surface plasmon resonance (SPR) has previously been employed to measure the active concentration of analyte in addition to the kinetic rate constants in molecular binding reactions. Those approaches, however, have a few restrictions. In this work, a Bayesian approach is developed to determine both active concentration and affinity constants using SPR technology. With the appropriate prior probabilities on the parameters and a derived likelihood function, a Markov Chain Monte Carlo (MCMC) algorithm is applied to compute the posterior probability densities of both the active concentration and kinetic rate constants based on the collected SPR data. Compared with previous approaches, ours exploits information from the duration of the process in its entirety, including both association and dissociation phases, under partial mass transport conditions; do not depend on calibration data; multiple injections of analyte at varying flow rates are not necessary. Finally the method is validated by analyzing both simulated and experimental datasets. A software package implementing our approach is developed with a user-friendly interface and made freely available.     

Protein fold recognition using segmentation conditional random fields (SCRFs).

Protein fold recognition is an important step towards understanding protein three-dimensional structures and their functions. A conditional graphical model, i.e., segmentation conditional random fields (SCRFs), is proposed as an effective solution to this problem. In contrast to traditional graphical models, such as the hidden Markov model (HMM), SCRFs follow a discriminative approach. Therefore, it is flexible to include any features in the model, such as overlapping or long-range interaction features over the whole sequence. The model also employs a convex optimization function, which results in globally optimal solutions to the model parameters. On the other hand, the segmentation setting in SCRFs makes their graphical structures intuitively similar to the protein 3-D structures and more importantly provides a framework to model the long-range interactions between secondary structures directly. Our model is applied to predict the parallel beta-helix fold, an important fold in bacterial pathogenesis and carbohydrate binding/cleavage. The cross-family validation shows that SCRFs not only can score all known beta-helices higher than non-beta-helices in the Protein Data Bank (PDB), but also accurately locates rungs in known beta-helix proteins. Our method outperforms BetaWrap, a state-of-the-art algorithm for predicting beta-helix folds, and HMMER, a general motif detection algorithm based on HMM, and has the additional advantage of general application to other protein folds. Applying our prediction model to the Uniprot Database, we identify previously unknown potential beta-helices.     

A Subsequent Fit of Time Series and Amplitude Histogram of Patch-Clamp Records Reveals Rate Constants up to 1 per Microsecond

Fast gating in time series of patch-clamp current demands powerful tools to reveal the rate constants of the adequate Hidden Markov model. Here, two approaches are presented to improve the temporal resolution of the direct fit of the time series. First, the prediction algorithm is extended to include intermediate currents between the nominal levels as caused by the anti-aliasing filter. This approach can reveal rate constants that are about 4 times higher than the corner frequency of the anti-aliasing filter. However, this approach is restricted to time series with very low noise. Second, the direct fit of the time series is combined with a beta fit, i.e., a fit of the deviations of the amplitude histogram from the Gaussian distribution. Since the “theoretical” amplitude histograms for higher-order Bessel filters cannot be calculated by analytical tools, they are generated from simulated time series. In a first approach, a simultaneous fit of the time series and of the Beta fit is tested. This simultaneous fit, however, inherits the drawbacks of both approaches, not the benefits. More successful is a subsequent fit: The fit of the time series yields a set of rate constants. The subsequent Beta fit uses the slow rate constants of the fit of the time series as fixed parameters and the optimization algorithm is restricted to the fast ones. The efficiency of this approach is illustrated by means of time series obtained from simulation and from the dominant K⁺ channel in Chara. This shows that temporal resolution can reach the microsecond range.     

Global parameter optimization for cardiac potassium channel gating models.

Quantitative ion channel model evaluation requires the estimation of voltage dependent rate constants. We have tested whether a unique set of rate constants can be reliably extracted from nonstationary macroscopic voltage clamp potassium current data. For many models, the rate constants derived independently at different membrane potentials are not unique. Therefore, our approach has been to use the exponential voltage dependence predicted from reaction rate theory (Stevens, C. F. 1978. Biophys. J. 22:295-306; Eyring, H., S. H. Lin, and S. M. Lin. 1980. Basic Chemical Kinetics. Wiley and Sons, New York) to couple the rate constants derived at different membrane potentials. This constrained the solution set of rate constants to only those that also obeyed this additional set of equations, which was sufficient to obtain a unique solution. We have tested this approach with data obtained from macroscopic delayed rectifier potassium channel currents in voltage-clamped guinea pig ventricular myocyte membranes. This potassium channel has relatively simple kinetics without an inactivation process and provided a convenient system to determine a globally optimized set of voltage-dependent rate constants for a Markov kinetic model. The ability of the fitting algorithm to extract rate constants from the macroscopic current data was tested using "data" synthesized from known rate constants. The simulated data sets were analyzed with the global fitting procedure and the fitted rate constants were compared with the rate constants used to generate the data. Monte Carlo methods were used to examine the accuracy of the estimated kinetic parameters. This global fitting approach provided a useful and convenient method for reliably extracting Markov rate constants from macroscopic voltage clamp data over a broad range of membrane potentials. The limitations of the method and the dependence on initial guesses are described.     

Accelerated Profile HMM Searches

Profile hidden Markov models (profile HMMs) and probabilistic inference methods have made important contributions to the theory of sequence database homology search. However, practical use of profile HMM methods has been hindered by the computational expense of existing software implementations. Here I describe an acceleration heuristic for profile HMMs, the "multiple segment Viterbi" (MSV) algorithm. The MSV algorithm computes an optimal sum of multiple ungapped local alignment segments using a striped vector-parallel approach previously described for fast Smith/Waterman alignment. MSV scores follow the same statistical distribution as gapped optimal local alignment scores, allowing rapid evaluation of significance of an MSV score and thus facilitating its use as a heuristic filter. I also describe a 20-fold acceleration of the standard profile HMM Forward/Backward algorithms using a method I call "sparse rescaling". These methods are assembled in a pipeline in which high-scoring MSV hits are passed on for reanalysis with the full HMM Forward/Backward algorithm. This accelerated pipeline is implemented in the freely available HMMER3 software package. Performance benchmarks show that the use of the heuristic MSV filter sacrifices negligible sensitivity compared to unaccelerated profile HMM searches. HMMER3 is substantially more sensitive and 100- to 1000-fold faster than HMMER2. HMMER3 is now about as fast as BLAST for protein searches.