Best match graphs characterize gene relatives in complex phylogenetic networks
Best Matches in Phylogenetic Networks
Discrete Mathematics
Summary
Finding closest relatives of genes in different species is important for understanding evolution, but traditional methods assume simple family trees. This paper extends the concept of 'best matches' to more complicated evolutionary networks where ancestors can be multiple or unclear. The authors provide a simple way to recognize these gene relationships efficiently and construct explanations for them in these networks. They also handle cases where relationships are mutual, called reciprocal best matches.
What this means in practice
- •For bioinformatics teams: Determine closest gene relatives across species using complex evolutionary networks to improve gene function prediction methods.
- •For computational biologists: Build and analyze rooted networks that explain gene similarity patterns beyond simple trees in large genomic datasets.
Authors
Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
Abstract
Best match graphs (BMGs) were introduced in mathematical phylogenetics to describe the concept of closest relatives for related genes (leaves of rooted tree) in different organisms (defining leaf colors). We generalize this concept here to leaf-colored rooted networks, where least common ancestors are in general neither unique nor comparable. We characterize BMGs of rooted networks as those vertex-colored digraphs that are properly colored and satisfy an easy-to-check condition that we call the sicor-in-hub property. BMGs can be recognized in linear time and an explaining network can be constructed in quadratic time. Analogous results are obtained for reciprocal best match graphs (RBMGs), where an edge $\{x,y\}$ corresponds to pairs of vertices with different color that are mutually closest relatives.