Separation of overlapping subpopulations by mutual information
Identifying ancestral sequences is an important first step in understanding population history and dynamics. However, several interesting cases including human genetic variation feature highly overlapping subpopulations, whose ancestral subpopulations differ by fewer than the average number of mutations between members of the same population. In such cases both flat and hierarchical distance-based clustering methods optimize the wrong objective function, and will therefore fail to recover the correct population structure. We present an algorithm for identifying substructure in overlapping populations based on the observation that variations at different sequence positions are uncorrelated. While motivated by a particular biological application, the algorithm can be applied to both discrete and continuous clustering problems for which distancebased measures are inappropriate. We demonstrate the algorithm’s effectiveness in reconstructing human subpopulations.