title: Clusterflock: a flocking algorithm for isolating congruent phylogenomic datasets.
abstract: Collective animal behavior, such as the flocking of birds or the shoaling of fish, has inspired a class of algorithms designed to optimize distance-based clusters in various applications, including document analysis and DNA microarrays. In a flocking model, individual agents respond only to their immediate environment and move according to a few simple rules. After several iterations the agents self-organize, and clusters emerge without the need for partitional seeds. In addition to its unsupervised nature, flocking offers several computational advantages, including the potential to reduce the number of required comparisons.
  
  
  
  In the tool presented here, Clusterflock, we have implemented a flocking algorithm designed to locate groups (flocks) of orthologous gene families (OGFs) that share an evolutionary history. Pairwise distances that measure phylogenetic incongruence between OGFs guide flock formation. We tested this approach on several simulated datasets by varying the number of underlying topologies, the proportion of missing data, and evolutionary rates, and show that in datasets containing high levels of missing data and rate heterogeneity, Clusterflock outperforms other well-established clustering techniques. We also verified its utility on a known, large-scale recombination event in Staphylococcus aureus. By isolating sets of OGFs with divergent phylogenetic signals, we were able to pinpoint the recombined region without forcing a pre-determined number of groupings or defining a pre-determined incongruence threshold.
  
  
  
  Clusterflock is an open-source tool that can be used to discover horizontally transferred genes, recombined areas of chromosomes, and the phylogenetic 'core' of a genome. Although we used it here in an evolutionary context, it is generalizable to any clustering problem. Users can write extensions to calculate any distance metric on the unit interval, and can use these distances to 'flock' any type of data.
authors: Sackler Institute for Comparative Genomics, American Museum of Natural History, New York, NY, 10024, USA.
authors: Apurva
authors: A
authors: Narechania
authors: Sackler Institute for Comparative Genomics, American Museum of Natural History, New York, NY, 10024, USA.
authors: Richard
authors: R
authors: Baker
authors: Sackler Institute for Comparative Genomics, American Museum of Natural History, New York, NY, 10024, USA.
authors: Rob
authors: R
authors: DeSalle
authors: Public Health Research Institute Center, New Jersey Medical School, Rutgers Newark, NJ, 07103, USA.|Department of Epidemiology, Mailman School of Public Health, Columbia University, New York, NY, 10032, USA.
authors: Barun
authors: B
authors: Mathema
authors: Sackler Institute for Comparative Genomics, American Museum of Natural History, New York, NY, 10024, USA.|Department of Biological Sciences, Fordham University, Bronx, NY, 10458, USA.
authors: Sergios-Orestis
authors: SO
authors: Kolokotronis
authors: Public Health Research Institute Center, New Jersey Medical School, Rutgers Newark, NJ, 07103, USA.
authors: Barry
authors: B
authors: Kreiswirth
authors: Sackler Institute for Comparative Genomics, American Museum of Natural History, New York, NY, 10024, USA. planetp@email.chop.edu.|Department of Pediatrics, Division of Pediatric Infectious Diseases, Children's Hospital of Philadelphia & University of Pennsylvania, Philadelphia, PA, 19104, USA. planetp@email.chop.edu.
authors: Paul J
authors: PJ
authors: Planet
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D019143:Evolution, Molecular; D005798:Genes, Bacterial; D023281:Genomics / Q000379:methods*; D010802:Phylogeny; D011995:Recombination, Genetic; D013211:Staphylococcus aureus / Q000145:classification* / Q000235:genetics
keywords: Data mining; Flocking algorithm; Horizontal gene transfer; Recombination; Staphylococcus aureus; Swarms; Unsupervised clustering