05276774

a

05276774 Zhu, Qian Adam, Zaky Choi, Vicky Sankoff, David Generalized gene adjacencies, graph bandwidth and clusters in yeast evolution. M\u andoiu, Ion (ed.) et al., Bioinformatics research and applications. Fourth international symposium, ISBRA 2008, Atlanta, GA, USA, May 6--9, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79449-3/pbk). Lecture Notes in Computer Science 4983. Lecture Notes in Bioinformatics, 134-145 (2008). 2008 Berlin: Springer EN

doi:10.1007/978-3-540-79450-9_13

Summary: We present a parametrized definition of gene clusters that allows us to control the emphasis placed on conserved order within a cluster. Though motivated by biological rather than mathematical considerations, this parameter turns out to be closely related to the maximum bandwidth parameter of a graph. Our focus will be on how this parameter affects the characteristics of clusters: how numerous they are, how large they are, how rearranged they are and to what extent they are preserved from ancestor to descendant in a phylogenetic tree. We infer the latter property by dynamic programming optimization of the presence of individual edges at the ancestral nodes of the phylogeny. We apply our analysis to a set of genomes drawn from the Yeast Gene Order Browser.