Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Best Match Graphs
Geiß, Manuela and Chávez, Edgar and González Laffitte, Marcos and Lopez Sánchez, Alitzel and Stadler, Bärbel M R and Valdivia, Dulce I. and Hellmuth, Marc and Hernández Rosales, Maribel and Stadler, Peter F
Download
Status: Published
J. Math. Biol. 78: 2015-2057
Abstract
Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and 𝜎 an assignment of leaves of T to species. The best match graph (𝐺,𝜎) is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species 𝜎(𝑦). Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether (𝐺,𝜎) derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains (𝐺,𝜎), which can also be constructed in cubic time.