Back to Search
Start Over
Best match graphs.
- Source :
-
Journal of mathematical biology [J Math Biol] 2019 Jun; Vol. 78 (7), pp. 2015-2057. Date of Electronic Publication: 2019 Apr 09. - Publication Year :
- 2019
-
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 [Formula: see text] an assignment of leaves of T to species. The best match graph [Formula: see text] 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 [Formula: see text]. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether [Formula: see text] derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains [Formula: see text], which can also be constructed in cubic time.
Details
- Language :
- English
- ISSN :
- 1432-1416
- Volume :
- 78
- Issue :
- 7
- Database :
- MEDLINE
- Journal :
- Journal of mathematical biology
- Publication Type :
- Academic Journal
- Accession number :
- 30968198
- Full Text :
- https://doi.org/10.1007/s00285-019-01332-9