Xu Jason, Minin Vladimir N
Department of Statistics, University of Washington, Seattle, WA 98195.
Departments of Statistics and Biology, University of Washington, Seattle, WA 98195.
Uncertain Artif Intell. 2015 Jul;2015:952-961.
Branching processes are a class of continuous-time Markov chains (CTMCs) with ubiquitous applications. A general difficulty in statistical inference under partially observed CTMC models arises in computing transition probabilities when the discrete state space is large or uncountable. Classical methods such as matrix exponentiation are infeasible for large or countably infinite state spaces, and sampling-based alternatives are computationally intensive, requiring integration over all possible hidden events. Recent work has successfully applied generating function techniques to computing transition probabilities for linear multi-type branching processes. While these techniques often require significantly fewer computations than matrix exponentiation, they also become prohibitive in applications with large populations. We propose a compressed sensing framework that significantly accelerates the generating function method, decreasing computational cost up to a logarithmic factor by only assuming the probability mass of transitions is sparse. We demonstrate accurate and efficient transition probability computations in branching process models for blood cell formation and evolution of self-replicating transposable elements in bacterial genomes.
分支过程是一类具有广泛应用的连续时间马尔可夫链（CTMC）。在部分观测的CTMC模型下进行统计推断时，当离散状态空间很大或不可数时，计算转移概率会出现一个普遍的困难。诸如矩阵求幂等经典方法对于大的或可数无限的状态空间是不可行的，而基于采样的替代方法计算量很大，需要对所有可能的隐藏事件进行积分。最近的工作已成功将生成函数技术应用于计算线性多类型分支过程的转移概率。虽然这些技术通常比矩阵求幂所需的计算量显著减少，但在大规模群体的应用中它们也变得令人望而却步。我们提出了一个压缩感知框架，该框架显著加速了生成函数方法，通过仅假设转移的概率质量是稀疏的，将计算成本降低到对数因子。我们在血细胞形成的分支过程模型以及细菌基因组中自我复制转座元件的进化中展示了准确且高效的转移概率计算。
