title: Unsupervised genome-wide recognition of local relationship patterns.
abstract: BACKGROUND
  Phenomena such as incomplete lineage sorting, horizontal gene transfer, gene duplication and subsequent sub- and neo-functionalisation can result in distinct local phylogenetic relationships that are discordant with species phylogeny. In order to assess the possible biological roles for these subdivisions, they must first be identified and characterised, preferably on a large scale and in an automated fashion.
  
  
  RESULTS
  We developed Saguaro, a combination of a Hidden Markov Model (HMM) and a Self Organising Map (SOM), to characterise local phylogenetic relationships among aligned sequences using cacti, matrices of pair-wise distance measures. While the HMM determines the genomic boundaries from aligned sequences, the SOM hypothesises new cacti in an unsupervised and iterative fashion based on the regions that were modelled least well by existing cacti. After testing the software on simulated data, we demonstrate the utility of Saguaro by testing two different data sets: (i) 181 Dengue virus strains, and (ii) 5 primate genomes. Saguaro identifies regions under lineage-specific constraint for the first set, and genomic segments that we attribute to incomplete lineage sorting in the second dataset. Intriguingly for the primate data, Saguaro also classified an additional ~3% of the genome as most incompatible with the expected species phylogeny. A substantial fraction of these regions was found to overlap genes associated with both the innate and adaptive immune systems.
  
  
  CONCLUSIONS
  Saguaro detects distinct cacti describing local phylogenetic relationships without requiring any a priori hypotheses. We have successfully demonstrated Saguaro's utility with two contrasting data sets, one containing many members with short sequences (Dengue viral strains: n = 181, genome size = 10,700 nt), and the other with few members but complex genomes (related primate species: n = 5, genome size = 3 Gb), suggesting that the software is applicable to a wide variety of experimental populations. Saguaro is written in C++, runs on the Linux operating system, and can be downloaded from http://saguarogw.sourceforge.net/.
authors.affiliation: Science for Life Laboratory, Department of Medical Biochemistry and Microbiology, Uppsala University, Uppsala, Sweden.
authors.forename: Neda
authors.initials: N
authors.lastname: Zamani
authors.forename: Pamela
authors.initials: P
authors.lastname: Russell
authors.forename: Henrik
authors.initials: H
authors.lastname: Lantz
authors.forename: Marc P
authors.initials: MP
authors.lastname: Hoeppner
authors.forename: Jennifer Rs
authors.initials: JR
authors.lastname: Meadows
authors.forename: Nagarjun
authors.initials: N
authors.lastname: Vijay
authors.forename: Evan
authors.initials: E
authors.lastname: Mauceli
authors.forename: Federica
authors.initials: F
authors.lastname: di Palma
authors.forename: Kerstin
authors.initials: K
authors.lastname: Lindblad-Toh
authors.forename: Patric
authors.initials: P
authors.lastname: Jern
authors.forename: Manfred G
authors.initials: MG
authors.lastname: Grabherr
mesh_terms: D000465:Algorithms; D000818:Animals; D003716:Dengue Virus / Q000235:genetics; D004196:Disease Outbreaks; D023281:Genomics / Q000379:methods*; D006801:Humans; D007109:Immunity / Q000235:genetics; D008390:Markov Chains; D008957:Models, Genetic; D010802:Phylogeny; D011323:Primates / Q000235:genetics / Q000276:immunology; D012984:Software; D013045:Species Specificity