by Thomas Mailund
I’m working on a project where it looks like I could end up with hidden Markov models with hundreds if not thousands of states, and with transition matrices where all entries are non-zero. Since, for such models, the running time for just calculating the likelihood (not even optimising it) is O(m . n^2) where m is the length of the input and n is the number of states, this could be a problem. Especially since I’m working on whole genome data, so m can get pretty large as well.
It is part of our CoalHMM work, but I’ll tell you more about that later. For this post, the actual application isn’t all that important, only the size of the model. So, anyway, needless to say I need a fast implementation if this is ever going to work.
