Abstract
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.
This work was supported in part by the German Research Foundation (DFG, STA 850/49-1) and the Data-driven Life Science (DDLS) program funded by the Knut and Alice Wallenberg Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Böcker, S., Dress, A.W.M.: Recovering symbolically dated, rooted trees from symbolic ultrametrics. Adv. Math. 138, 105–125 (1998). https://doi.org/10.1006/aima.1998.1743
Corneil, D.G., Lerchs, H., Steward Burlingham, L.: Complement Reducible Graphs. Discr. Appl. Math. 3, 163–174 (1981)
Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14, 926–934 (1985)
Crespelle, C., Paul, C.: Fully dynamic recognition algorithm and certificate for directed cographs. Discr. Appl. Math. 154, 1722–1741 (2006)
Engelfriet, J., Harju, T., Proskurowski, A., Rozenberg, G.: Characterization and complexity of uniformly nonprimitive labeled 2-structures. Theor. Comp. Sci. 154, 247–282 (1996)
Geiß, M., Anders, J., Stadler, P.F., Wieseke, N., Hellmuth, M.: Reconstructing gene trees from fitch’s xenology relation. J. Math. Biol. 77, 1459–1491 (2018). https://doi.org/10.1007/s00285-018-1260-8
Gurski, F.: Dynamic programming algorithms on directed cographs. Stat. Optim. Inf. Comput. 5(1), 35–44 (2017). https://doi.org/10.19139/soic.v5i1.260
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
Hellmuth, M., Seemann, C.R.: Alternative characterizations of Fitch’s xenology relation. J. Math. Biol. 79(3), 969–986 (2019). https://doi.org/10.1007/s00285-019-01384-x
Hellmuth, M., Stadler, P.F., Puthiyaveedu, S.T.: Fitch graph completion (2023). https://doi.org/10.48550/arXiv.2306.06878
Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5, 558–562 (1962). https://doi.org/10.1145/368996.369025
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). https://doi.org/10.1007/978-1-4684-2001-2_9
McConnell, R.M., De Montgolfier, F.: Linear-time modular decomposition of directed graphs. Discr. Appl. Math. 145(2), 198–209 (2005). https://doi.org/10.1016/j.dam.2004.02.017
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). https://doi.org/10.1007/978-3-319-94776-1_34
Ravenhall, M., Škunca, N., Lassalle, F., Dessimoz, C.: Inferring horizontal gene transfer. PLoS Comp. Biol. 11, e1004095 (2015). https://doi.org/10.1371/journal.pcbi.1004095
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hellmuth, M., Stadler, P.F., Thekkumpadan Puthiyaveedu, S. (2024). Fitch Graph Completion. In: Wu, W., Tong, G. (eds) Computing and Combinatorics. COCOON 2023. Lecture Notes in Computer Science, vol 14423. Springer, Cham. https://doi.org/10.1007/978-3-031-49193-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-031-49193-1_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49192-4
Online ISBN: 978-3-031-49193-1
eBook Packages: Computer ScienceComputer Science (R0)