Quantifying Hierarchical Conflicts in Homology Statements.

A fundamental step in any comparative gene-order analysis is the annotation of homology relationships between segments of the genomes. Whether this annotation comes in the form of homologous genes or homologous segments inferred from a de novo whole genome alignment (WGA), annotations that are roughly collocated in many genomes can be agglomerated into homologous syntenic blocks. In this article we develop a test that measures the extent to which two different sets of homology relationships are hierarchically related to one another, where matched segments from one set may contain matched segments from the other and vice versa. Such a test should be used as a sanity check for an agglomerative syntenic block software, and provides a mapping between the blocks that can be used for further downstream analyses. We show that, in practice, it is rare that two collections of homology relationships are perfectly hierarchically related. This motivates an optimization problem, which is a generalization of the assignment problem, that measures how far they are from being hierarchically related. We give an algorithm that solves this problem in linear time on a tree, serving as the core of a heuristic applied to a general graph. We apply our distance measure to data from the Alignathon competition, as well as to Mycobacterium tuberculosis isolates, showing that many factors affect how hierarchically related two collections are, including sensitivities to guide trees and synteny inference parameter settings. These findings inform practitioners on the pitfalls of homology relationship inference, and should help in further development of robust inference tools.