Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming

Héctor Corrada Bravo, Stephen J. Wright, Kevin H. Eng, Sündüz Keles, Grace Wahba

Introduction

In evolutionary biology and phylogenetics, understanding the hierarchical relationships between variables—such as gene expression levels—is a fundamental challenge. These relationships are typically modeled using tree-structured covariance matrices, where the covariance between two variables is proportional to the shared path length from their common ancestor. Traditional methods for estimating these trees often rely on a two-step heuristic: first computing pairwise distances and then applying algorithms like Neighbor-Joining. However, these heuristics do not guarantee global optimality and can be sensitive to noise in continuous data. This paper introduces a novel approach that treats tree topology estimation as a discrete optimization problem, solved using Mixed-Integer Programming (MIP).

Methodology: A Projection Approach

The authors frame the estimation as a projection problem: given an observed sample covariance matrix $S$, find the "nearest" tree-structured matrix $B$ that minimizes a chosen norm (e.g., Frobenius or sum-absolute-value).

A key innovation is the mathematical representation of the tree-structured matrix. The matrix $B$ is decomposed as $VDV^T$, where $V$ is a basis matrix representing nested partitions (branches) and $D$ is a diagonal matrix of branch lengths. To ensure $V$ represents a valid tree, the authors define a "Partition Property." By introducing binary variables to act as "switches" for these partitions, the combinatorial search for the optimal topology is transformed into a MIP. This allows the use of powerful solvers like CPLEX to find the globally optimal tree structure.

Correspondence between a tree topology (a) and its structured covariance matrix (b).

Simulation and Performance

The efficacy of the MIP approach was first tested using simulated data. Trees of size 10 were generated, and data was sampled from a Wishart distribution with varying degrees of freedom. The results demonstrate that as the sample size increases, the MIP-based methods (using both Frobenius and sum-absolute-value norms) converge to the true tree topology. In contrast, the standard Neighbor-Joining heuristic fails to recover the correct structure even with large amounts of data, highlighting the limitations of greedy, distance-based approaches.

Mean topological distance from the true tree as a function of sample size (degrees of freedom). The MIP methods converge to zero error, while Neighbor-Joining plateaus.

Biological Application: Yeast Gene Families

The method was applied to real-world gene expression data from Saccharomyces cerevisiae. The researchers analyzed 19 cDNA microarray experiments across 10 gene families. A significant finding was the introduction of "structural strength" ($SS(B)$), a metric quantifying how well a dataset fits a tree model. Gene families previously identified as having strong phylogenetic signals exhibited significantly higher structural strength than those that did not.

In a specific case study of the ABC Transporter family, the MIP-derived tree based on expression data differed from traditional sequence-based trees. Further analysis revealed that the expression-based tree's topology correlated with shared transcription factor binding sites (specifically PDR3). This suggests that the MIP method can capture functional evolutionary signals that sequence-based methods might overlook.

Conclusion and Future Directions

The MIP-based approach offers a robust framework for estimating tree-structured covariance matrices by ensuring global optimality. While currently limited by the computational complexity of integer programming as the number of variables grows, it provides a powerful tool for small-to-medium-sized trees. Future work aims to extend this framework to Maximum Likelihood Estimation and to develop more formal statistical tests for tree-like structure in high-dimensional datasets.

Summary updated

Abstract

We present a novel method for estimating tree-structured covariance matrices directly from observed continuous data. Specifically, we estimate a covariance matrix from observations of p continuous random variables encoding a stochastic process over a tree with p leaves. A representation of these classes of matrices as linear combinations of rank-one matrices indicating object partitions is used to formulate estimation as instances of well-studied numerical optimization problems.In particular, our estimates are based on projection, where the covariance estimate is the nearest tree-structured covariance matrix to an observed sample covariance matrix. The problem is posed as a linear or quadratic mixed-integer program (MIP) where a setting of the integer variables in the MIP specifies a set of tree topologies of the structured covariance matrix. We solve these problems to optimality using efficient and robust existing MIP solvers.We present a case study in phylogenetic analysis of gene expression and a simulation study comparing our method to distance-based tree estimating procedures.
BibTeX
@article{bravo2009estimating,
  author = {Héctor Corrada Bravo and Stephen J. Wright and Kevin H. Eng and Sündüz Keles and Grace Wahba},
  title = {{Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming}},
  journal = {AISTATS},
  year = {2009},
}
Figure