Skip Navigation



Bioinformatics Advance Access published online on March 4, 2009
Bioinformatics, doi:10.1093/bioinformatics/btp109
This Article
Right arrow Advance Access manuscript (PDF)
Right arrow Supplementary Data
Right arrow Supplementary Data
Right arrow All Versions of this Article:
25/9/1165    most recent
btp109v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by King, B. M.
Right arrow Articles by Tidor, B.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by King, B. M.
Right arrow Articles by Tidor, B.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2009). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

MIST: Maximum Information Spanning Trees for Dimension Reduction of Biological Data Sets

Bracken M. King 1,2 and Bruce Tidor 1,2,3,*

1Computer Science and Artificial Intelligence Laboratory, 2Department of Biological Engineering, 3Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA

*To whom correspondence should be addressed. Dr. Bruce Tidor, E-mail: tidor{at}mit.edu


  Abstract

Motivation: The study of complex biological relationships is aided by large and high-dimensional data sets whose analysis often involves dimension reduction to highlight representative or informative directions of variation. In principle, information theory provides a general framework for quantifying complex statistical relationships for dimension reduction. Unfortunately, direct estimation of highdimensional information theoretic quantities, such as entropy and mutual information (MI), is often unreliable given the relatively small sample sizes available for biological problems. Here we develop and evaluate a hierarchy of approximations for high-dimensional information theoretic statistics from associated low-order terms, which can be more reliably estimated from limited samples. Due to a relationship between this metric and the minimum spanning tree over a graph representation of the system, we refer to these approximations as MIST (Maximum Information Spanning Trees).

Results: The MIST approximations are examined in the context of synthetic networks with analytically computable entropies and using experimental gene expression data as a basis for the classification of multiple cancer types. The approximations result in significantly more accurate estimates of entropy and MI, and also correlate better with biological classification error than direct estimation and another low-order approximation, minimum-redundancy-maximum-relevance (mRMR).

Availability: Software to compute the entropy approximations described here is available as Supplementary Material.

Contact: tidor{at}mit.edu

Associate Editor: Dr. Jonathan Wren

Received on October 5, 2008; revised on February 9, 2009; accepted on February 22, 2009

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.