OMG! Orthologs in Multiple Genomes - Competing graph-theoretical formulations

Chunfang Zheng, Krister Swenson, Eric Lyons, David Sankoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations


From the set of all pairwise homologies, weighted by sequence similarities, among a set of genomes, we seek disjoint orthology sets of genes, in which each element is orthogonal to all other genes (on a different genome) in the same set. In a graph-theoretical formulation, where genes are vertices and weighted edges represent homologies, we suggest three criteria, with three different biological motivations, for evaluating the partition of genes produced by deletion of a subset of edges: i) minimum weight edge removal, ii) minimum degree-zero vertex creation, and iii) maximum number of edges in the transitive closure of the graph after edge deletion. For each of the problems, all either proved or conjectured to be NP-hard, we suggest approximate and heuristic algorithms of finding orthology sets satisfying the criteria, and show how to incorporate genomes that have a whole genome duplication event in their immediate lineage. We apply this to ten flowering plant genomes, involving 160,000 different genes in given pairwise homologies. We evaluate the results in a number of ways and recommend criterion iii) as best suited to applications to multiple gene order alignment.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 11th International Workshop, WABI 2011, Proceedings
Number of pages12
ISBN (Print)9783642230370
StatePublished - 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6833 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'OMG! Orthologs in Multiple Genomes - Competing graph-theoretical formulations'. Together they form a unique fingerprint.

Cite this