Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution

ABSTRACT

We present a parameterized 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 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.

REFERENCES

• 1: Anne Bergeron , Sylvie Corteel , Mathieu Raffinot, The Algorithmic of Gene Teams, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.464-476, September 17-21, 2002
• 2: K.P. Byrne and K.H. Wolfe, "The Yeast Gene Order Browser: Combining Curated Homology and Syntenic Context Reveals Gene Fate in Polyploid Species," Genome Research, vol. 15, pp. 1456-1461, 2005.
• 3: B. Dujon et al., "Genome Evolution in Yeasts," Nature, vol. 430, pp. 35-44, 2004.
• 4: J. Felsenstein, Inferring Phylogenies. Sinauer Assoc., 2004.
• 5: A. George, "Computer Implementation of the Finite Element Method," Technical Report STAN-CS-71-208, Computer Science Dept., Stanford Univ., 1971.
• 6: E.M. Gurari and I.H. Sudborough, "Improved Dynamic Programming Algorithms for Bandwidth Minimization and the Mincut Linear Arrangement Problem," J. Algorithms, vol. 5, pp. 531-546, 1984.
• 7: R. Hoberman, D. Sankoff, and D. Durand, "The Statistical Analysis of Spatially Clustered Genes under the Maximum Gap Criterion," J. Computational Biology, vol. 12, pp. 1081-1100, 2005.
• 8: J. Liu and A. Sherman, "Comparative Analysis of the Cuthill-Mckee and the Reverse Cuthill-Mckee Ordering Algorithms for Sparse Matrices," SIAM J. Numerical Analysis, vol. 13, pp. 198-213, 1975.
• 9: C.H. Papadimitriou, "The NP-Completeness of the Bandwidth Minimization Problem," Computing, vol. 16, pp. 263-270, 1976.
• 10: J. Saxe, "Dynamic-Programming Algorithms for Recognizing Small-Band-Width Graphs in Polynomial Time," SIAM J. Algebraic and Discrete Methods, vol. 1, pp. 363-369, 1980.
• 11: Ximing Xu , David Sankoff, Tests for Gene Clusters Satisfying the Generalized Adjacency Criterion, Proceedings of the 3rd Brazilian symposium on Bioinformatics: Advances in Bioinformatics and Computational Biology, August 28-30, 2008, Santo André, Brazil [doi>10.1007/978-3-540-85557-6_14]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods; Dynamic programming
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Design, Theory

Keywords:
Comparative genomics, gene clusters, yeast, evolution, phylogeny, genome rearrangements, graph bandwidth, dynamic programming, Saccharomyces cerevisiae, Candida glabrata, Ashbya gossypii, Kluyveromyces waltii, Kluyveromyces lactis.