Best match graphs.

Autor: Geiß M; Bioinformatics Group, Department of Computer Science, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany.; Interdisciplinary Center of Bioinformatics, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany., Chávez E; CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico., González Laffitte M; CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico., López Sánchez A; CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico., Stadler BMR; Max-Planck-Institute for Mathematics in the Sciences, Inselstraße 22, 04103, Leipzig, Germany., Valdivia DI; Centro de Ciencias Básicas, Universidad Autónoma de Aguascalientes, Av. Universidad 940, 20131, Aguascalientes, AGS, Mexico.; Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico., Hellmuth M; Institute of Mathematics and Computer Science, University of Greifswald, Walther-Rathenau-Straße 47, 17487, Greifswald, Germany.; Center for Bioinformatics, Saarland University, Building E 2.1, P.O. Box 151150, 66041, Saarbrücken, Germany., Hernández Rosales M; CONACYT-Instituto de Matemáticas, UNAM Juriquilla, Blvd. Juriquilla 3001, 76230, Juriquilla, Querétaro, QRO, Mexico., Stadler PF; Bioinformatics Group, Department of Computer Science, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; Interdisciplinary Center of Bioinformatics, University of Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; Max-Planck-Institute for Mathematics in the Sciences, Inselstraße 22, 04103, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; Competence Center for Scalable Data Services and Solutions, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; Leipzig Research Center for Civilization Diseases, Leipzig University, Härtelstraße 16-18, 04107, Leipzig, Germany. studla@bioinf.uni-leipzig.de.; Institute of Theoretical Chemistry, University of Vienna, Währingerstraße 17, 1090, Vienna, Austria. studla@bioinf.uni-leipzig.de.; Facultad de Ciencias, Universidad National de Colombia, Sede Bogotá, Colombia. studla@bioinf.uni-leipzig.de.; Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM, 87501, USA. studla@bioinf.uni-leipzig.de.
Jazyk: angličtina
Zdroj: Journal of mathematical biology [J Math Biol] 2019 Jun; Vol. 78 (7), pp. 2015-2057. Date of Electronic Publication: 2019 Apr 09.
DOI: 10.1007/s00285-019-01332-9
Abstrakt: 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.
Databáze: MEDLINE
Externí odkaz: