We give an algorithm for discovering co-evolution in biosequences from a dataset consisting of aligned data and a phylogeny. The method correlates vectors of parsimony scores on the edges of a graph, averaged over all optimally parsimonious reconstructions of the data. We describe an efficient data structure, and a preprocessing step that allows for rapid, interactive computation of many correlation scores, at the expense of storage space.
Get full access to this article
View all access options for this article.
References
1.
BlanchetteM.2002. Algorithms for phylogenetic footprinting. J. Comput. Biol., 9, 211–224.
2.
FitchW.M.1971. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool., 20, 406–416.
3.
GlazierA.M., NadeauJ.H., and AitmanT.J.2002. Finding genes that underlie complex traits. Science, 298, 2345–2349.
4.
JothiR., KannM.G., and PrzytyckaT.M.2005. Predicting protein-protein interaction by searching evolutionary tree automorphism space. Bioinformatics, 21, Suppl 1, 241–250.
5.
KimY., KoyutürkM., TopkaraU., et al.2006. Inferring functional information from domain co-evolution. Bioinformatics, 22, 40–49.
6.
LiX., ChenH., HuangZ., et al.2007. Global mapping of gene/protein interactions in pubmed abstracts: a framework and an experiment with p53 interactions. J. Biomed. Inform., 40, 453–464.
7.
RamaniA.K., and MarcotteE.M.2003. Exploiting the co-evolution of interacting proteins to discover interaction specificity. J. Mol. Biol., 327, 273–284.
TamayoA.G., BhartiA., TrujilloC., et al.2008. Copi coatomer complex proteins facilitate the translocation of anthrax lethal factor across vesicular membranes in vitro. Proc. Nat. Acad. Sci. U.S.A.
10.
TukeyJ.W.1975. Mathematics and the picturing of data. Proc. Int. Congr. Math., 2, 523–531.
