MOTIVATION: Human pluripotent stem cell lines persist in culture as a heterogeneous population of SSEA3 positive and SSEA3 negative cells. Tracking individual stem cells in real time can elucidate the kinetics of cells switching between the SSEA3 positive and negative substates. However, identifying a cell's substate at all time points within a cell lineage tree is technically difficult. RESULTS: A variational Bayesian Expectation Maximization (EM) with smoothed probabilities (VBEMS) algorithm for hidden Markov trees (HMT) is proposed for incomplete tree structured data. The full posterior of the HMT parameters is determined and the underflow problems associated with previous algorithms are eliminated. Example results for the prediction of the types of cells in synthetic and real stem cell lineage trees are presented. AVAILABILITY: The Matlab code for the VBEMS algorithm is freely available at http://www.acse.dept.shef.ac.uk/repository/vbems_lineage_tree/VBEMS.ZIP CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.