function [Tree,pred] = Phylogeny (F)
% Infer a phylogeny from mixture fractions
% F is the matrix of mixture fractions (rows=samples and columns=components) 
% Tree is the sparse adjacency matrix corresponding to the inferred phylogeny
% pred is the vector of ancestors of nodes in the phylogeny
% Code is copyright Russell Schwartz, Carnegie Mellon University 2009

% Convert fraction matrix F into a weight matrix of fractional sharing
W=sparse(zeros(size(F,2),size(F,2)));
S=sum(F,1);
for i=1:(size(F,2))
 for j=1:(size(F,2))
  for k=1:size(F,1)
   W(i,j)=W(i,j)+F(k,i)*F(k,j)/S(i)/S(j);
  end
  if (W(i,j)<1e-10)
    W(i,j)=1e-10;
  end
 end
end

% Convert sharing fractions to log likelihoods
W=-log(W);

% Scale to eliminate negative-weight edges
m=min(min(W));
W=W-m;

% Find a minimum spanning tree of F
[Tree,pred]=graphminspantree(W);
