title: Estimating Tree-Structured Covariance Matrices via Mixed-Integer Programming.
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.
authors.affiliation: Department of Biostatistics, Johns Hopkins Bloomberg, School of Public Health, Baltimore, MD 21205.
authors.forename: Héctor Corrada
authors.initials: HC
authors.lastname: Bravo
authors.forename: Stephen
authors.initials: S
authors.lastname: Wright
authors.forename: Kevin H
authors.initials: KH
authors.lastname: Eng
authors.forename: Sündüz
authors.initials: S
authors.lastname: Keles
authors.forename: Grace
authors.initials: G
authors.lastname: Wahba
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2008 Jul-Sep;5(3):323-31
references.pmid: 18670037
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2006 Apr-Jun;3(2):141-54
references.pmid: 17048400
references.citation: Mol Biol Evol. 1987 Jul;4(4):406-25
references.pmid: 3447015
references.citation: Nat Genet. 2003 Feb;33(2):138-44
references.pmid: 12548287
references.citation: PLoS Biol. 2004 Dec;2(12):e398
references.pmid: 15534694
references.citation: Science. 2003 Oct 10;302(5643):249-55
references.pmid: 12934013
references.citation: Genetics. 2004 May;167(1):531-42
references.pmid: 15166175
references.citation: Bioinformatics. 2004 Jan 22;20(2):289-90
references.pmid: 14734327
references.citation: Mol Biol Evol. 2002 Mar;19(3):256-62
references.pmid: 11861885
references.citation: Mol Biol Evol. 2005 Jan;22(1):40-50
references.pmid: 15356281
references.citation: Evolution. 1967 Sep;21(3):550-570
references.pmid: 28563688
references.citation: FEBS Lett. 2006 Feb 13;580(4):1131-8
references.pmid: 16406363
references.citation: Proc Natl Acad Sci U S A. 2006 Apr 4;103(14):5425-30
references.pmid: 16567645
references.citation: Heredity (Edinb). 2008 Feb;100(2):191-9
references.pmid: 17519966
references.citation: Mol Gen Genet. 1994 Sep 1;244(5):501-11
references.pmid: 8078477