Clustering ionic flow blockade toggles with a mixture of HMMs.
BACKGROUND
Ionic current blockade signal processing, for use in nanopore detection, offers a promising new way to analyze single molecule properties with potential implications for DNA sequencing. The alpha-Hemolysin transmembrane channel interacts with a translocating molecule in a nontrivial way, frequently evidenced by a complex ionic flow blockade pattern with readily distinguishable modes of toggling. Effective processing of such signals requires developing machine learning methods capable of learning the various blockade modes for classification and knowledge discovery purposes. Here we propose a method aimed to improve our stochastic analysis capabilities to better understand the discriminatory capabilities of the observed the nanopore channel interactions with analyte.


RESULTS
We tailored our memory-sparse distributed implementation of a Mixture of Hidden Markov Models (MHMMs) to the problem of channel current blockade clustering and associated analyte classification. By using probabilistic fully connected HMM profiles as mixture components we were able to cluster the various 9 base-pair hairpin channel blockades. We obtained very high Maximum a Posteriori (MAP) classification with a mixture of 12 different channel blockade profiles, each with 4 levels, a configuration that can be computed with sufficient speed for real-time experimental feedback. MAP classification performance depends on several factors such as the number of mixture components, the number of levels in each profile, and the duration of a channel blockade event. We distribute Baum-Welch Expectation Maximization (EM) algorithms running on our model in two ways. A distributed implementation of the MHMM data processing accelerates data clustering efforts. The second, simultanteous, strategy uses an EM checkpointing algorithm to lower the memory use and efficiently distribute the bulk of EM processing in processing large data sequences (such as for the progressive sums used in the HMM parameter estimates).


CONCLUSIONS
The proposed distributed MHMM method has many appealing properties, such as precise classification of analyte in real-time scenarios, and the ability to incorporate new domain knowledge into a flexible, easily distributable, architecture. The distributed HMM provides a feature extraction that is equivalent to that of the sequential HMM with a speedup factor approximately equal to the number of independent CPUs operating on the data. The MHMM topology learns clusters existing within data samples via distributed HMM EM learning. A Java implementation of the MHMM algorithm is available at http://logos.cs.uno.edu/~achurban.
Churbanov
Alexander
A
The Research Institute for Children, 200 Henry Clay Ave, New Orleans, LA 70118, USA. atchourb@cs.uno.edu
Winters-Hilt
Stephen
S
D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D001681:Biological Assay / Q000379:methods*; D004247:DNA / Q000737:chemistry*; D029968:Escherichia coli Proteins / Q000737:chemistry* / Q000235:genetics*; D006460:Hemolysin Proteins / Q000737:chemistry* / Q000235:genetics*; D015640:Ion Channel Gating / Q000235:genetics*; D007473:Ion Channels / Q000032:analysis / Q000737:chemistry* / Q000235:genetics*; D008390:Markov Chains; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*
D029968:Escherichia coli Proteins; D006460:Hemolysin Proteins; C036507:Hlya protein, E coli; D007473:Ion Channels; D004247:DNA
BMC Bioinformatics. 2006 Sep 06;7 Suppl 2:S15
17118136
Nat Biotechnol. 2001 Mar;19(3):248-52
11231558
Biophys J. 2007 Nov 1;93(9):3229-40
17675346
BMC Bioinformatics. 2005 Sep 19;6:231
16171529
J Mol Biol. 1994 Feb 4;235(5):1501-31
8107089
Biophys J. 2006 Jan 1;90(1):190-9
16214857
Biophys J. 2003 Feb;84(2 Pt 1):967-76
12547778
Bioinformatics. 1998 Jun;14(5):401-6
9682053
Comput Appl Biosci. 1997 Feb;13(1):45-53
9088708
Biol Direct. 2006 Apr 03;1:10
16584568
BMC Bioinformatics. 2008 Apr 30;9:224
18447951
Proc Natl Acad Sci U S A. 1994 Dec 20;91(26):12828-31
7809129
Bioinformatics. 2000 Dec;16(12):1082-90
11159327
Biophys J. 1999 Dec;77(6):3227-33
10585944
BMC Bioinformatics. 2007 Nov 01;8 Suppl 7:S14
18047713