Efficient Projection onto the Perfect Phylogeny Model
Several algorithms build on the perfect phylogeny model to infer evolutionary trees. This problem is particularly hard when evolutionary trees are inferred from the fraction of genomes that have mutations in different positions, across different samples. Existing algorithms might do extensive searches over the space of possible trees. At the center of these algorithms is a projection problem that assigns a fitness cost to phylogenetic trees. In order to perform a wide search over the space of the trees, it is critical to solve this projection problem fast. In this paper, we use Moreau's decomposition for proximal operators, and a tree reduction scheme, to develop a new algorithm to compute this projection. Our algorithm terminates with an exact solution in a finite number of steps, and is extremely fast. In particular, it can search over all evolutionary trees with fewer than 11 nodes, a size relevant for several biological problems (more than 2 billion trees) in about 2 hours.
This paper attempts to solve an optimization subproblem which arises in a matrix factorization which arises in studying the phylogenetic evolutionary tree.  In particular, the overall problem is given a matrix F, find the matrices U and M such that F=UM where U is a binary matrix and M is a positive matrix whose columns sum to 1.  The subproblem is, given U, to find the least-squares solution F,M such that || \hat{F} - F || is minimized subject to the constraints that F = UM where \hat{F} is the measured matrix.  The paper proposes an algorithm which can solve this subproblem directly in polynomial time (compared with iterative solvers) and the major contribution is the algorithm for computing this along with the theoretical proofs of its optimality.  Beyond this analysis, practical techniques are proposed for evaluating the algorithm efficiently.  The algorithm is then applied and compared against current state-of-the-art iterative solvers, specifically ADMM and PGD.  Experimental results show that the proposed algorithm is dramatically faster in practice when compared against existing iterative solvers.  Overall the paper seems well written and the results significant.  I suspect the paper will be of interest beyond those studying phyolgenetic trees as the main contribution is related to the optimization sub problem.   UPDATE: Having read the author feedback I remain largely positive on the paper.  In addition, the authors included additional experimental comparison against other methods seems to be a very positive and compelling addition to the paper.