Fitch graph completion. (English) Zbl 07900444
Wu, Weili (ed.) et al., Computing and combinatorics. 29th international conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14423, 225-237 (2024).
Summary: Horizontal gene transfer is an important contributor to evolution. According to Walter M. Fitch, two genes are xenologs if they are separated by at least one HGT. More formally, the directed Fitch graph has a set of genes as its vertices, and directed edges \((x, y)\) for all pairs of genes \(x\) and \(y\) for which \(y\) has been horizontally transferred at least once since it diverged from the last common ancestor of \(x\) and \(y\). Subgraphs of Fitch graphs can be inferred by comparative sequence analysis. In many cases, however, only partial knowledge about the “full” Fitch graph can be obtained. Here, we characterize Fitch-satisfiable graphs that can be extended to a biologically feasible “full” Fitch graph and derive a simple polynomial-time recognition algorithm. We then proceed to showing that finding the Fitch graphs with total maximum (confidence) edge-weights is an NP-hard problem.
For the entire collection see [Zbl 1543.68019].
For the entire collection see [Zbl 1543.68019].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
Keywords:
directed cograph; Fitch graph; horizontal gene transfer; NP-complete; recognition algorithmReferences:
| [1] | Böcker, S.; Dress, AWM, Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math., 138, 105-125, 1998 · Zbl 0912.05031 · doi:10.1006/aima.1998.1743 |
| [2] | Corneil, DG; Lerchs, H.; Steward Burlingham, L., Complement Reducible Graphs. Discr., Appl. Math., 3, 163-174, 1981 · Zbl 0463.05057 |
| [3] | Corneil, DG; Perl, Y.; Stewart, LK, A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934, 1985 · Zbl 0575.68065 · doi:10.1137/0214065 |
| [4] | Crespelle, C.; Paul, C., Fully dynamic recognition algorithm and certificate for directed cographs, Discr. Appl. Math., 154, 1722-1741, 2006 · Zbl 1110.68096 · doi:10.1016/j.dam.2006.03.005 |
| [5] | Engelfriet, J.; Harju, T.; Proskurowski, A.; Rozenberg, G., Characterization and complexity of uniformly nonprimitive labeled 2-structures, Theor. Comp. Sci., 154, 247-282, 1996 · Zbl 0873.68161 · doi:10.1016/0304-3975(94)00272-X |
| [6] | Geiß, M.; Anders, J.; Stadler, PF; Wieseke, N.; Hellmuth, M., Reconstructing gene trees from fitch’s xenology relation, J. Math. Biol., 77, 1459-1491, 2018 · Zbl 1396.05025 · doi:10.1007/s00285-018-1260-8 |
| [7] | Gurski, F., Dynamic programming algorithms on directed cographs, Stat. Optim. Inf. Comput., 5, 1, 35-44, 2017 · doi:10.19139/soic.v5i1.260 |
| [8] | Hellmuth, M., Scholz, G.E.: Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs (2023). http://arxiv.org/abs/10.48550/arXiv.2211.16854 |
| [9] | Hellmuth, M.; Seemann, CR, Alternative characterizations of Fitch’s xenology relation, J. Math. Biol., 79, 3, 969-986, 2019 · Zbl 1420.92082 · doi:10.1007/s00285-019-01384-x |
| [10] | Hellmuth, M., Stadler, P.F., Puthiyaveedu, S.T.: Fitch graph completion (2023). doi:10.48550/arXiv.2306.06878 |
| [11] | Kahn, AB, Topological sorting of large networks, Commun. ACM, 5, 558-562, 1962 · Zbl 0106.32602 · doi:10.1145/368996.369025 |
| [12] | Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, pp. 85-103. Springer, US, Boston, MA (1972). doi:10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [13] | McConnell, RM; De Montgolfier, F., Linear-time modular decomposition of directed graphs, Discr. Appl. Math., 145, 2, 198-209, 2005 · Zbl 1055.05123 · doi:10.1016/j.dam.2004.02.017 |
| [14] | Nøjgaard, N., El-Mabrouk, N., Merkle, D., Wieseke, N., Hellmuth, M.: Partial homology relations - satisfiability in terms of di-cographs. In: Wang, L., Zhu, D. (eds.) Computing and Combinatorics. Lecture Notes Comp. Sci., vol. 10976, pp. 403-415. Springer, Cham (2018). doi:10.1007/978-3-319-94776-1_34 · Zbl 1512.92056 |
| [15] | Ravenhall, M.; Škunca, N.; Lassalle, F.; Dessimoz, C., Inferring horizontal gene transfer, PLoS Comp. Biol., 11, e1004095, 2015 · doi:10.1371/journal.pcbi.1004095 |
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.
