×

Best match graphs with binary trees. (English) Zbl 1480.92153

Martín-Vide, Carlos (ed.) et al., Algorithms for computational biology. 8th international conference, AlCoB 2021, Missoula, MT, USA, June 7–11, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12715, 82-93 (2021).
Summary: Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-resolvable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG.
For the entire collection see [Zbl 1476.92001].

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aho, AV; Sagiv, Y.; Szymanski, TG; Ullman, JD, Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM J. Comput., 10, 405-421 (1981) · Zbl 0462.68086 · doi:10.1137/0210030
[2] Bryant, D.: Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis. Dissertation, University of Canterbury, Canterbury, NZ (1997)
[3] Bryant, D.; Steel, M., Extension operations on sets of leaf-labeled trees, Adv. Appl. Math., 16, 4, 425-453 (1995) · Zbl 0863.92012 · doi:10.1006/aama.1995.1020
[4] Deng, Y.; Fernández-Baca, D., Fast compatibility testing for rooted phylogenetic trees, Algorithmica, 80, 8, 2453-2477 (2017) · Zbl 1392.68451 · doi:10.1007/s00453-017-0330-4
[5] Geiß, M.; Anders, J.; Stadler, PF; Wieseke, N.; Hellmuth, M., Reconstructing gene trees from Fitch’s xenology relation, J. Math. Biol., 77, 5, 1459-1491 (2018) · Zbl 1396.05025 · doi:10.1007/s00285-018-1260-8
[6] Geiß, M., Best match graphs, J. Math. Biol., 78, 7, 2015-2057 (2019) · Zbl 1415.92133 · doi:10.1007/s00285-019-01332-9
[7] Geiß, M., Best match graphs and reconciliation of gene trees with species trees, J. Math. Biol., 80, 5, 1459-1495 (2020) · Zbl 1434.05035 · doi:10.1007/s00285-020-01469-y
[8] Grünewald, S.; Steel, M.; Swenson, MS, Closure operations in phylogenetics, Math. Biosci., 208, 521-537 (2007) · Zbl 1119.92048 · doi:10.1016/j.mbs.2006.11.005
[9] He, YJ; Huynh, TND; Jansson, J.; Sung, WK, Inferring phylogenetic relationships avoiding forbidden rooted triplets, J. Bioinf. Comp. Biol., 4, 59-74 (2006) · doi:10.1142/S0219720006001709
[10] Henzinger, MR; King, V.; Warnow, T., Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology, Algorithmica, 24, 1-13 (1999) · Zbl 0936.68026 · doi:10.1007/PL00009268
[11] Keller-Schmidt, S.; Klemm, K., A model of macroevolution as a branching process based on innovations, Adv. Complex Syst., 15, 1250043 (2012) · doi:10.1142/S0219525912500439
[12] Nichio, BTL; Marchaukoski, JN; Raittz, RT, New tools in orthology analysis: a brief review of promising perspectives, Front. Genet., 8, 165 (2017) · doi:10.3389/fgene.2017.00165
[13] Rusin, L.Y., Lyubetskaya, E., Gorbunov, K.Y., Lyubetsky, V.: Reconciliation of gene and species trees. BioMed. Res. Int. 2014 (2014). doi:10.1155/2014/642089
[14] Schaller, D., et al.: Corrigendum to “Best Match Graphs”. J. Math. Biol. In press (2021). arxiv.org/1803.10989v4, doi:10.1016/j.tcs.2021.02.037 · Zbl 07340472
[15] Schaller, D., Geiß, M., Hellmuth, M., Stadler, P.F.: Best Match Graphs with Binary Trees. Tech. Rep. 2011.00511 arxiv.org/2011.00511 (2020) · Zbl 1460.92149
[16] Schaller, D.; Geiß, M.; Stadler, PF; Hellmuth, M., Complete characterization of incorrect orthology assignments in best match graphs, J. Math. Biol., 82, 3, 1-64 (2021) · Zbl 1460.92149 · doi:10.1007/s00285-021-01564-8
[17] Schaller, D., Stadler, P.F., Hellmuth, M.: Complexity of modification problems for best match graphs. Theor. Comp. Sci. 865, 63-84 (2021). doi:10.1016/j.tcs.2021.02.037 · Zbl 1500.92068
[18] Seemann, CR; Hellmuth, M., The matroid structure of representative triple sets and triple-closure computation, Eur. J. Comb., 70, 384-407 (2018) · Zbl 1384.05066 · doi:10.1016/j.ejc.2018.02.013
[19] Semple, C., Reconstructing minimal rooted trees, Discr. Appl. Math., 127, 489-503 (2003) · Zbl 1038.05014 · doi:10.1016/S0166-218X(02)00250-0
[20] Semple, C.; Steel, M., Phylogenetics (2003), Oxford UK: Oxford University Press, Oxford UK · Zbl 1043.92026
[21] Setubal, J.C., Stadler, P.F.: Gene phyologenies and orthologous groups. In: Setubal, J.C., Stadler, P.F., Stoye, J. (eds.) Comparative Genomics, vol. 1704, pp. 1-28. Springer, Heidelberg (2018). doi:10.1007/978-1-4939-7463-4_1
[22] Slowinski, JB, Molecular polytomies, Mol. Phylogenet. Evol., 19, 1, 114-120 (2001) · doi:10.1006/mpev.2000.0897
[23] Stadler, PF, From pairs of most similar sequences to phylogenetic best matches, Alg. Mol. Biol., 15, 5 (2020) · doi:10.1186/s13015-020-00165-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.