Pith. sign in

REVIEW 1 major objections 4 minor 77 references

Orthology and Near-Cographs in the Context of Phylogenetic Networks

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A graph is level-1 explainable if and only if every primitive induced subgraph is a near-cograph.

desk verdict A clean, carefully argued characterization of level-1 explainable orthology graphs, with a linear-time algorithm; the main caveat is that the proof leans on imported theorems and a slightly nonstandard definition of level-1. read the letter →

arxiv 2502.08746 v1 pith:AS6G4QMV submitted 2025-02-12 q-bio.PE cs.DMmath.CO

Anna Lindeberg , Guillaume E. Scholz , Nicolas Wieseke , Marc Hellmuth This is my paper · ORCID
classification q-bio.PEcs.DMmath.CO MSC 05C8505C7592D15
keywords orthologygraphlevel-1networknear-cographmodulardecompositionphylogenetictwin-widthperfectlinear-timealgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Orthology graphs inferred under a tree-like model must be cographs, but real data often are not, and network-like evolution is a natural explanation. This paper establishes that the graphs explainable by a level-1 phylogenetic network—one where each biconnected block contains at most one reticulation—are exactly the graphs whose primitive induced subgraphs are near-cographs, meaning deletion of a single vertex leaves a cograph. The same class is characterized via modular decomposition (all non-trivial prime quotients must be near-cographs) and via closure under disjoint union, join, and vertex substitution, and it can be recognized and realized by a network in linear time. So the paper converts a question about evolutionary feasibility into a structural graph problem, showing that level-1 reticulation relaxes the cograph condition in a precise, algorithmically tractable way.

What carries the argument

The machinery is modular decomposition together with prime-vertex replacement: the modular decomposition tree of $G$ organizes the strong modules into series, parallel, and prime nodes, and each prime module $M$ is represented by its quotient graph $G[M]/M_{\max}(G[M])$. The key step is Theorem 4.12, which shows that a primitive graph is level-1 explainable exactly when it is a primitive near-cograph; the proof reduces a primitive level-1 network to a regular, 2-lca-relevant network (one in which every vertex is a least common ancestor of some one- or two-leaf set) with a single hybrid leaf, and then removes that leaf to obtain a cotree. Near-cographs are the atomic graphs: a graph from which one vertex deletion gives a cograph, where a cograph is a graph with no induced $P_4$ built from disjoint unions and joins. Prime-vertex replacement networks then assemble a level-1 network for the whole graph by substituting each prime quotient with such an atomic network inside the modular decomposition tree.

What would settle it

Take the 5-cycle $C_5$: deleting any one vertex leaves a path on four vertices, which is not a cograph, so $C_5$ is primitive and not a near-cograph; the theorem predicts that no level-1 network with speciation labels can explain it. Finding such a network would refute the central claim.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 4.20: a graph $G$ is level-1 explainable if and only if every primitive induced subgraph of $G$ is a near-cograph. A near-cograph is a graph from which removing one vertex yields a cograph, and a cograph is a graph with no induced path on four vertices ($P_4$). The characterization is shown to be equivalent to the statement that, for every non-trivial prime module $M$ of the modular decomposition, the quotient graph $G[M]/M_{\max}(G[M])$ is a near-cograph (Theorem 4.19), and to the statement that $G$ can be built from single vertices and primitive near-cographs using disjoint unions, joins, and vertex substitution (Theorems 4.24 and 4.26). The paper further proves that level-1 explainable graphs are weakly chordal and hence perfect, and that they have twin-width at most 2, so algorithmic tools for those graph classes apply to them.

Load-bearing premise

The load-bearing premise is that any level-1 explainable graph can be explained by a regular level-1 network whose clusters faithfully encode all pairwise least common ancestors, and that level-1 networks are exactly those whose cluster systems are closed and satisfy the technical property (L); if these imported equivalences fail, or hold only for the generalized level-1 definition that allows hybrid leaves, the near-cograph criterion may not transfer to standard networks.

Editorial extensions

If this is right

  • Every graph is level-$k$ explainable for some $k<|X|$, so for large $k$ the network model imposes no structural restriction; the level-1 condition is where a meaningful, testable constraint appears.
  • Any graph containing an induced cycle or anti-cycle on $n\ge 5$ vertices is not level-1 explainable, since such subgraphs are primitive and not near-cographs.
  • The class of level-1 explainable graphs is hereditary and closed under disjoint unions, joins, and vertex substitution, giving a recursive grammar whose atoms are single vertices and primitive near-cographs.
  • There is an $O(|X|+|E|)$-time algorithm that recognizes level-1 explainable graphs and, if possible, constructs an explaining level-1 network.
  • Level-1 explainable graphs are weakly chordal, perfect, and have twin-width at most 2, placing them in known algorithmic regimes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: since every graph is explainable at some level, the biologically meaningful boundary is the number of reticulation events per block; level-1 is the only level that still yields a non-trivial graph class, so comparing inferred orthology graphs against this class can serve as a test for 'almost tree-like' evolution.
  • Editorial inference: the characterization suggests a new editing problem—turn an input orthology graph into the nearest level-1 explainable graph—whose complexity the paper leaves open; such an algorithm would be a network-aware alternative to cograph editing for data cleaning.
  • Editorial inference: the modular-decomposition-plus-replacement strategy is a plausible template for level-2 and higher networks, but the paper's Figure 5 shows that a second hybrid can change the primitive graphs substantially, so a level-2 characterization would require genuinely new structural control rather than a routine extension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies graphs that can be explained by 0/1-labeled phylogenetic level-1 networks (LEV-1-EX graphs), motivated by orthology graphs. The central result is Theorem 4.20: a graph is LEV-1-EX if and only if every primitive induced subgraph is a near-cograph. Equivalent characterizations are also given in terms of prime quotient graphs being near-cographs (Theorem 4.19), phylogenetic level-1 explainability (Theorem 4.21), and closure under substitution and atomic expressions (Theorems 4.24 and 4.26). The paper further shows that every graph is explainable by some level-k network with k < |X| (Theorem 3.10), provides a linear-time recognition and construction algorithm (Theorem 4.22), and proves that LEV-1-EX graphs are weakly chordal, perfect, and of twin-width at most 2 (Theorem 4.29 and Proposition 4.30).

Significance. If the result holds, this is a substantial contribution to the theory of orthology graphs under network-like evolution: it extends the tree/cograph characterization to the level-1 network setting in a clean, modular-decomposition way. The proof structure is transparent, with the primitive case (Theorem 4.12) proved by explicit network constructions and then lifted to arbitrary graphs via prime-vertex replacement networks. The linear-time algorithm is a concrete algorithmic payoff, and the graph-class consequences (weakly chordal, perfect, twin-width at most 2) give falsifiable structural predictions. The main caveat is that the primitive-case reduction relies on imported structural characterizations of level-1 networks from [42] and [47]; within the paper's own definitional framework the derivation is coherent, and no circularity was found.

major comments (1)
  1. [§2, Definition 2.2; §3.2, Theorem 3.6; §4.2, Lemma 4.7] Lemma 4.7, which is load-bearing for the central characterization, assumes that an arbitrary level-1 explainable graph can be represented by a regular, 2-lca-relevant level-1 network (Theorem 3.6, via [42, Thm. 3.12]) and that level-1 network cluster systems are exactly the closed systems satisfying property (L) (Theorem 2.12, imported from [47]). Since Definition 2.2 deliberately generalizes the customary notion of level-1 networks by allowing hybrid leaves, the paper should state explicitly that Theorem 2.12 and the level-1 results of [47] are valid for this generalized class, or else prove the needed direction for hybrid leaves. As written, the conclusion of Lemma 4.7 that the unique hybrid can be taken to be a leaf, and therefore Theorems 4.19 and 4.20, inherits this external assumption; the transfer to the stricter standard level-1 class is not established. This is a scope and correctness clarification rather than an internal contradiction, but it is load-bearing and should be addressed in the revision.
minor comments (4)
  1. [§3.2, Theorem 3.10 and thereafter] The abbreviation LEV-k-EX is used starting from Theorem 3.10 and throughout Section 4, but it appears not to be formally defined; please add a definition near Definition 3.1 or at the first use of LEV-k-EX.
  2. [§4.4, Theorem 4.22 proof] The final sentence of the proof reads 'In summary, can be verified in O(|X|+|E|) time'; the subject 'it' is missing and should be restored.
  3. [§4.1, modular decomposition] In the definition of series and parallel strong modules, the text appears to print 'G[M] is disconnected' in both cases; the series case should refer to the complement graph, so please check the typesetting of the overline.
  4. [§4.3, Definition 4.15] The condition for two networks to be internal vertex-disjoint should be that the displayed intersection is empty; the printed '=/0' is easy to misread as nonempty and should be typeset unambiguously as the empty set.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the LEV-1-EX characterizations are derived from independent network-cluster and modular-decomposition lemmas, not from their own conclusions.

full rationale

The paper's central claim, that LEV-1-EX graphs are exactly those whose primitive induced subgraphs are near-cographs (Theorem 4.20), is a genuine equivalence between two independently defined notions: explainability by a 0/1-labeled level-1 network (Definition 3.1, Definition 2.2) and near-cographness (Definition 4.8). The proof path goes through Theorem 4.12, whose forward direction uses Lemma 4.7 to force a primitive LEV-1-EX graph to have exactly one hybrid leaf, then removes that hybrid and shows the remaining cluster system is a hierarchy by Theorem 2.11. This is a real structural reduction, not a restatement of the target. Lemma 4.7 itself invokes Theorem 3.6 and Theorem 2.12, which are imported from [42] and [47]; these are parameter-free mathematical characterizations of DAGs and level-1 cluster systems that do not mention near-cographs or LEV-1-EX, so citing them is legitimate independent support rather than a circular chain. Similarly, Theorems 4.19, 4.24, and 4.26 follow from modular-decomposition facts (Lemma 4.3, Proposition 4.17, Lemma 4.18) and the primitive case, with no fitted parameters and no definition that presupposes the result. The paper does contain substantial self-citation, especially from [42], [58], and [47], but none of the load-bearing uses reduces to the authors' own conclusion; they are auxiliary structural lemmas. The algorithmic result (Theorem 4.22) is also supported by independent linear-time cograph recognition and modular decomposition routines. Therefore no circular step is present, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the standard 0/1-labeled LCA model for orthology and on several structural theorems imported from previous papers by the same research group ([42], [47], [58]). These are mathematical results, not fitted parameters or invented entities, but their correctness is not re-derived here, so the verification of the main theorem depends on that prior work. The paper introduces no free parameters and no new postulated entities.

assumptions (5)
  • domain assumption Orthology graphs are modeled by 0/1-labeled DAGs with the 2-lca property, where an edge exists iff the label of the least common ancestor is 1 (Definition 3.1, based on [45]).
    This is the standard mathematical model the entire paper operates in; it is an assumption from the field, not derived here.
  • domain assumption A clustering system is the cluster system of a level-1 network if and only if it is closed and satisfies property (L) (Theorem 2.12, imported from [47]).
    The proofs of Theorems 4.12 and 4.19 flow through cluster systems; this prior characterization is load-bearing and not re-proven.
  • domain assumption Every level-1 explainable graph can be explained by a regular, 2-lca-relevant level-1 network (Theorem 3.6, via [42, Thm. 3.12]).
    Lemma 4.7 depends on this reduction to constrain the network structure for primitive graphs.
  • domain assumption For any lca-network explaining G, an induced subgraph G[W] is explained by the Hasse diagram of the restricted cluster system (Proposition 3.5, imported from [58]).
    This is used in Theorem 4.12 to show G - h is a cograph, and in Proposition 4.14 for the hereditary property.
  • domain assumption The pvr-network construction explains any graph given a prime-explaining family (Proposition 4.17, imported from [58]).
    Theorems 4.19 and 4.21 build the level-1 network from prime-explaining families using this result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Orthology and Near-Cographs in the Context of Phylogenetic Networks." pith.science (2026). https://pith.science/paper/AS6G4QMV

@misc{pith2026250208746,
  author       = {Pith},
  title        = {Pith review of: Orthology and Near-Cographs in the Context of Phylogenetic Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AS6G4QMV}},
  note         = {Machine review of arXiv:2502.08746}
}
read the original abstract

Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the underlying gene or species trees. This results in orthology graphs, where each vertex represents a gene, and an edge exists between two vertices if the corresponding genes are estimated to be orthologs. Orthology graphs inferred under a tree-like evolutionary model must be cographs. However, real-world data often deviate from this property, either due to noise in the data, errors in inference methods or, simply, because evolution follows a network-like rather than a tree-like process. The latter, in particular, raises the question of whether and how orthology graphs can be derived from or, equivalently, are explained by phylogenetic networks. Here, we study the constraints imposed on orthology graphs when the underlying evolutionary history follows a phylogenetic network instead of a tree. We show that any orthology graph can be represented by a sufficiently complex level-k network. However, such networks lack biologically meaningful constraints. In contrast, level-1 networks provide a simpler explanation, and we establish characterizations for level-1 explainable orthology graphs, i.e., those derived from level-1 evolutionary histories. To this end, we employ modular decomposition, a classical technique for studying graph structures. Specifically, an arbitrary graph is level-1 explainable if and only if each primitive subgraph is a near-cograph (a graph in which the removal of a single vertex results in a cograph). Additionally, we present a linear-time algorithm to recognize level-1 explainable orthology graphs and to construct a level-1 network that explains them, if such a network exists.

Figures

Figures reproduced from arXiv: 2502.08746 by the authors.

Figure 1
Figure 1. Shown are four 0/1-labeled DAGs (N,t), (N ′ ,t ′ ), (N ′′ ,t ′′) and (Ne,t˜) that all explain the graph G. Here, N, N ′ and N ′′ are networks while Ne is not. Since G ≃ P4, Theorem 3.3 implies that G cannot be explained by a 0/1-labeled tree. The network (N,t) is a “half-grid” (cf. [10]) and is level-3, whereas (N ′ ,t ′ ) is a regular level-2 network with N ′ .= H(CG) where CG is chosen according to Equation (1). T… view at source ↗
Figure 2
Figure 2. A 0/1-labeled level-1 network (N,t) where G = G(N,t) consists of k > 1 vertex disjoint induced P4s. If G−Y is a cograph, then Y ⊆ V(G) with |Y| ≥ k > 1 must hold. Theorem 3.6. Let G = (X,E) be a graph explained by a 0/1-labeled network (N,t) and define C({1,2}) := {C ∈ CN : C is the unique inclusion-minimal cluster in CN containing A for some A ⊆ X, |A| ∈ {1,2}}. Then, H(C({1,2})) is a regular DAG that is 2-lca-rele… view at source ↗
Figure 3
Figure 3. Example for Definition 3.7, constructing the shown 0/1-labeled network (N↖v,t↖v) from the level-1 network (N,t) as shown in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Shown is a graph G that is explained by several 0/1-labeled level-1 networks: (N,t), (N ′ ,t ′ ), and (N ′′ ,t ′′). Note that G is a near-cograph as G−d is a cograph. Here, (N,t) is a pvr-network obtained from the MDT (TG, τG) of G by replacing the prime(P)-labeled ver…
Figure 5
Figure 5. Figure 5: A primitive graph G = G(N,t) that is explained by the 0/1-labeled level-2 network (N,t). Here, there is no subset Y ⊆ V(G) of size |Y| ≤ 2 such that G−Y is a cograph. To see this, assume, for contradiction, that there is a set Y of size |Y| ≤ 2 resulting in the cograph…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 56 canonical work pages

  1. [47]

    Theory in Biosciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w

    Hellmuth M, Schaller D, Stadler PF (2023) Clustering systems of phylogenetic networks. Theory in Biosciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w

    doi:10.1007/s12064-023-00398-w 2023

  2. [42]

    URL https://arxiv.org/abs/2411.14057, 2411.14057

    Hellmuth M, Lindeberg A (2024) Characterizing and transforming DAGs within the I-LCA framework. URL https://arxiv.org/abs/2411.14057, 2411.14057

    arXiv 2024

  3. [1]

    URLhttps://arxiv.org/ abs/2501.00991, 2501.00991

    Ahn J, Jacob H, K ¨ohler N, Paul C, Reinald A, Wiederrecht S (2025) Twin-width one. URLhttps://arxiv.org/ abs/2501.00991, 2501.00991

    arXiv 2025

  4. [2]

    DOI 10.1007/978-1-4939-9074-0 5 21

    Altenhoff AM, Glover NM, Dessimoz C (2019) Inferring Orthology and Paralogy, Springer New York, New York, NY , pp 149–175. DOI 10.1007/978-1-4939-9074-0 5 21

    work page doi:10.1007/978-1-4939-9074-0 2019

  5. [3]

    Proceedings of the American Mathematical Society 54(1):468–470, DOI 10.1090/S0002-9939-1976-0505776-7

    Aschbacher M (1976) A homomorphism theorem for finite graphs. Proceedings of the American Mathematical Society 54(1):468–470, DOI 10.1090/S0002-9939-1976-0505776-7

    work page doi:10.1090/s0002-9939-1976-0505776-7 1976

  6. [4]

    Ann Comb 8:391–408, DOI 10.1007/s00026-004-0228-0

    Baroni M, Semple C, Steel M (2005) A framework for representing reticulate evolution. Ann Comb 8:391–408, DOI 10.1007/s00026-004-0228-0

    doi:10.1007/s00026-004-0228-0 2005

  7. [5]

    Journal of Graph Theory 2(1):19–24, DOI 10.1002/jgt

    Blass A (1978) Graphs with unique maximal clumpings. Journal of Graph Theory 2(1):19–24, DOI 10.1002/jgt. 3190020104

    doi:10.1002/jgt 1978

  8. [6]

    J ACM 69(1):46, DOI 10.1145/3486655

    Bonnet E, Kim EJ, Thomass ´e S, Watrigant R (2021) Twin-width I: Tractable FO Model Checking. J ACM 69(1):46, DOI 10.1145/3486655

    doi:10.1145/3486655 2021

Show all 77 references
  1. [7]

    SIAM Journal on Computing 53(5):1602–1640, DOI 10.1137/21M142188X

    Bonnet E, Geniet C, Kim EJ, Thomass´e S, Watrigant R (2024) Twin-width III: Max independent set, min dominating set, and coloring. SIAM Journal on Computing 53(5):1602–1640, DOI 10.1137/21M142188X

    2024 doi

  2. [8]

    SIAM, DOI 10.1137/1.9780898719796

    Brandst ¨adt A, Le VB, Spinrad JP (1999) Graph Classes: A Survey. SIAM, DOI 10.1137/1.9780898719796

    1999 doi

  3. [9]

    Discrete Applied Mathematics 257:60–66, DOI 10.1016/j.dam.2018.10.030

    Brignall R, Choi H, Jeong J, il Oum S (2019) Deciding whether there are infinitely many prime graphs with forbid- den induced subgraphs. Discrete Applied Mathematics 257:60–66, DOI 10.1016/j.dam.2018.10.030

    2019 doi

  4. [10]

    Discrete Applied Mathematics 310:1–9, DOI 10.1016/j.dam.2021.12.017

    Bruckmann C, Stadler PF, Hellmuth M (2022) From modular decomposition trees to rooted median graphs. Discrete Applied Mathematics 310:1–9, DOI 10.1016/j.dam.2021.12.017

    2022 doi

  5. [11]

    LIRMM, Universite Montpellier, rapport de recherche 94073

    Capelle C, Cournier A, Habib M (1994) Cograph recognition algorithm revisited and online induced P4 search. LIRMM, Universite Montpellier, rapport de recherche 94073

    1994

  6. [12]

    Molecular systems biology 12(5):872, DOI 10.15252/msb.20156777

    Chandrasekaran S, Cokol-Cakmak M, Sahin N, Yilancioglu K, Kazan H, Collins JJ, Cokol M (2016) Chemoge- nomics and orthology-based design of antibiotic combination therapies. Molecular systems biology 12(5):872, DOI 10.15252/msb.20156777

    2016 doi

  7. [13]

    Discrete Applied Mathematics 3(3):163–174, DOI 10.1016/0166-218X(81)90013-5

    Corneil D, Lerchs H, Burlingham LS (1981) Complement reducible graphs. Discrete Applied Mathematics 3(3):163–174, DOI 10.1016/0166-218X(81)90013-5

    1981 doi

  8. [14]

    SIAM Journal on Computing 14(4):926–934, DOI 10.1137/0214065

    Corneil DG, Perl Y , Stewart LK (1985) A linear recognition algorithm for cographs. SIAM Journal on Computing 14(4):926–934, DOI 10.1137/0214065

    1985 doi

  9. [15]

    Cournier A, Habib M (1994) A new linear algorithm for modular decomposition. In: Tison S (ed) Trees in Algebra and Programming — CAAP’94, Lecture Notes in Computer Science, vol 787, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 68–84, DOI 10.1007/BFb0017474

    1994 doi

  10. [16]

    Discrete Mathematics 183(1):61–80, DOI 10.1016/ S0012-365X(97)00077-0

    Cournier A, Ille P (1998) Minimal indecomposable graphs. Discrete Mathematics 183(1):61–80, DOI 10.1016/ S0012-365X(97)00077-0

    1998

  11. [17]

    In: Comparative Genomics: RECOMB 2005 International Workshop, RCG 2005, Dublin, Ireland, Septem- ber 18-20, 2005

    Dessimoz C, Cannarozzi G, Gil M, Margadant D, Roth A, Schneider A, Gonnet GH (2005) Oma, a comprehensive, automated project for the identification of orthologs from complete genome data: introduction and first achieve- ments. In: Comparative Genomics: RECOMB 2005 International...

    2005 doi

  12. [18]

    Procedia computer science 108:1115–1124, DOI 10.1016/j.procs.2017.05.047

    Dondi R, Mauri G, Zoppis I (2017) Orthology correction for gene tree reconstruction: Theoretical and experimental results. Procedia computer science 108:1115–1124, DOI 10.1016/j.procs.2017.05.047

    2017 doi

  13. [19]

    European Journal of Combinatorics 32(8):1317– 1328, DOI 10.1016/j.ejc.2011.05.001

    Drgas-Burchardt E (2011) On prime inductive classes of graphs. European Journal of Combinatorics 32(8):1317– 1328, DOI 10.1016/j.ejc.2011.05.001

    2011 doi

  14. [20]

    Discrete Applied Mathematics 291:201–222, DOI 10.1016/j.dam.2020.12.018

    Ducoffe G, Popa A (2021) The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. Discrete Applied Mathematics 291:201–222, DOI 10.1016/j.dam.2020.12.018

    2021 doi

  15. [21]

    American Journal of Mathematics 63(3):600–610, DOI 10

    Dushnik B, Miller EW (1941) Partially ordered sets. American Journal of Mathematics 63(3):600–610, DOI 10. 2307/2371374

    1941

  16. [22]

    Theoretical Computer Science 70(3):343–358, DOI 10.1016/0304-3975(90)90131-Z

    Ehrenfeucht A, Rozenberg G (1990) Primitivity is hereditary for 2-structures. Theoretical Computer Science 70(3):343–358, DOI 10.1016/0304-3975(90)90131-Z

    1990 doi

  17. [23]

    Theo- retical Computer Science 70(3):277–303, DOI 10.1016/0304-3975(90)90129-6

    Ehrenfeucht A, Rozenberg G (1990) Theory of 2-structures, part I: Clans, basic subclasses, and morphisms. Theo- retical Computer Science 70(3):277–303, DOI 10.1016/0304-3975(90)90129-6

    1990 doi

  18. [24]

    Theoretical Computer Science 70(3):305–342, DOI 10.1016/0304-3975(90)90130-A 22

    Ehrenfeucht A, Rozenberg G (1990) Theory of 2-structures, part II: Representation through labeled tree families. Theoretical Computer Science 70(3):305–342, DOI 10.1016/0304-3975(90)90130-A 22

    1990 doi

  19. [25]

    Journal of Algorithms 16(2):283–294, DOI 10.1006/jagm.1994.1013

    Ehrenfeucht A, Gabow H, Mcconnell R, Sullivan S (1994) An O( n2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Journal of Algorithms 16(2):283–294, DOI 10.1006/jagm.1994.1013

    1994

  20. [26]

    Genome research 8(3):163–167, DOI 10.1101/gr.8.3.163

    Eisen JA (1998) Phylogenomics: improving functional predictions for uncharacterized genes by evolutionary anal- ysis. Genome research 8(3):163–167, DOI 10.1101/gr.8.3.163

    1998 doi

  21. [27]

    Theoretical Computer Science 154(2):247–282, DOI 10.1016/0304-3975(94)00272-X

    Engelfriet J, Harju T, Proskurowski A, Rozenberg G (1996) Characterization and complexity of uniformly nonprim- itive labeled 2-structures. Theoretical Computer Science 154(2):247–282, DOI 10.1016/0304-3975(94)00272-X

    1996 doi

  22. [28]

    Syst Zool 19:99–113, DOI 10.2307/ 2412448

    Fitch WM (1970) Distinguishing homologous from analogous proteins. Syst Zool 19:99–113, DOI 10.2307/ 2412448

    1970

  23. [29]

    Trends Genet 16:227–231, DOI 10.1016/ S0168-9525(00)02005-9

    Fitch WM (2000) Homology: a personal view on some of the problems. Trends Genet 16:227–231, DOI 10.1016/ S0168-9525(00)02005-9

    2000

  24. [30]

    Briefings in bioinformatics 12(5):463–473, DOI 10.1093/bib/bbr024

    Forslund K, Schreiber F, Thanintorn N, Sonnhammer EL (2011) Orthodisease: tracking disease gene orthologs across 100 species. Briefings in bioinformatics 12(5):463–473, DOI 10.1093/bib/bbr024

    2011 doi

  25. [31]

    Art of Discrete and Applied Mathematics 3(2), DOI 10.26493/2590-9770.1252.e71

    Fritz A, Hellmuth M, Stadler PF, Wieseke N (2020) Cograph editing: Merging modules is equivalent to editing P4s. Art of Discrete and Applied Mathematics 3(2), DOI 10.26493/2590-9770.1252.e71

    2020

  26. [32]

    Acta Mathematica Academiae Scientiarum Hungarica 18(1):25– 66, DOI 10.1007/BF02020961

    Gallai T (1967) Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica 18(1):25– 66, DOI 10.1007/BF02020961

    1967 doi

  27. [33]

    J Math Biol 78:2015–2057, DOI 10.1007/s00285-019-01332-9

    Geiß M, Ch ´avez E, Gonz´alez Laffitte M, L´opez S´anchez A, Stadler BMR, Valdivia DI, Hellmuth M, Hern´andez Ros- ales M, Stadler PF (2019) Best match graphs. J Math Biol 78:2015–2057, DOI 10.1007/s00285-019-01332-9

    2019 doi

  28. [34]

    Journal of Mathematical Biology 80(5):1459–1495, DOI 10

    Geiß M, Laffitte MEG, S ´anchez AL, Valdivia DI, Hellmuth M, Rosales MH, Stadler PF (2020) Best match graphs and reconciliation of gene trees with species trees. Journal of Mathematical Biology 80(5):1459–1495, DOI 10. 1007/s00285-020-01469-y

    2020

  29. [35]

    Theoretical Computer Science 370(1):74–93, DOI 10.1016/j.tcs.2006.10.024

    Giakoumakis V , Olariu S (2007) All minimal prime extensions of hereditary classes of graphs. Theoretical Computer Science 370(1):74–93, DOI 10.1016/j.tcs.2006.10.024

    2007 doi

  30. [36]

    Discrete Applied Mathematics 9(2):157–170, DOI 10.1016/0166-218X(84)90016-7

    Golumbic MC, Monma CL, Trotter WT (1984) Tolerance graphs. Discrete Applied Mathematics 9(2):157–170, DOI 10.1016/0166-218X(84)90016-7

    1984 doi

  31. [37]

    BMC bioinformatics 12:1–9, DOI 10.1186/1471-2105-12-S1-S15

    G ´orecki P, Burleigh GJ, Eulenstein O (2011) Maximum likelihood models and algorithms for gene tree evolution with duplications and losses. BMC bioinformatics 12:1–9, DOI 10.1186/1471-2105-12-S1-S15

    2011 doi

  32. [38]

    Mol Biol Evol 1:57–66, DOI 10.1093/oxfordjournals.molbev.a040298

    Gray GS, Fitch WM (1983) Evolution of antibiotic resistance genes: The DNA sequence of a kanamycin resistance gene from Staphylococcus aureus. Mol Biol Evol 1:57–66, DOI 10.1093/oxfordjournals.molbev.a040298

    1983 doi

  33. [39]

    In: Berge C, Chv ´atal V (eds) Topics on Perfect Graphs, North-Holland Mathematics Studies, vol 88, North-Holland, pp 325–356, DOI 10.1016/S0304-0208(08)72943-8

    Gr ¨otschel M, Lov ´asz L, Schrijver A (1984) Polynomial algorithms for perfect graphs. In: Berge C, Chv ´atal V (eds) Topics on Perfect Graphs, North-Holland Mathematics Studies, vol 88, North-Holland, pp 325–356, DOI 10.1016/S0304-0208(08)72943-8

    1984 doi

  34. [40]

    Computer Science Review 4(1):41–59, DOI 10.1016/j.cosrev.2010.01.001

    Habib M, Paul C (2010) A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1):41–59, DOI 10.1016/j.cosrev.2010.01.001

    2010 doi

  35. [41]

    Journal of Combinatorial Theory, Series B 39(3):200–208, DOI 10.1016/0095-8956(85)90050-4

    Hayward RB (1985) Weakly triangulated graphs. Journal of Combinatorial Theory, Series B 39(3):200–208, DOI 10.1016/0095-8956(85)90050-4

    1985 doi

  36. [43]

    Discrete Applied Mathematics 321:179–219, DOI 10.1016/j.dam.2022.06.042

    Hellmuth M, Scholz GE (2022) From modular decomposition trees to level-1 networks: Pseudo-cographs, polar- cats and prime polar-cats. Discrete Applied Mathematics 321:179–219, DOI 10.1016/j.dam.2022.06.042

    2022 doi

  37. [44]

    Discrete Applied Mathematics 343:25–43, DOI 10.1016/j.dam.2023.09.034

    Hellmuth M, Scholz GE (2024) Resolving prime modules: The structure of pseudo-cographs and galled-tree ex- plainable graphs. Discrete Applied Mathematics 343:25–43, DOI 10.1016/j.dam.2023.09.034

    2024 doi

  38. [45]

    J Math Biol 66(1-2):399–420, DOI 10.1007/s00285-012-0525-x

    Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V , Stadler PF, Wieseke N (2013) Orthology relations, symbolic ultrametrics, and cographs. J Math Biol 66(1-2):399–420, DOI 10.1007/s00285-012-0525-x

    2013 doi

  39. [46]

    PNAS 112(7):2058–2063, DOI 10.1073/pnas.1412770112 23

    Hellmuth M, Wieseke N, Lechner M, Lenhof HP, Middendorf M, Stadler PF (2015) Phylogenomics with paralogs. PNAS 112(7):2058–2063, DOI 10.1073/pnas.1412770112 23

    2015 doi

  40. [48]

    Algorithmica 80(1):73–103, DOI 10.1007/s00453-016-0241-9

    Huber KT, Scholz GE (2018) Beyond representing orthology relations by trees. Algorithmica 80(1):73–103, DOI 10.1007/s00453-016-0241-9

    2018 doi

  41. [49]

    Cam- bridge University Press

    Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cam- bridge University Press

    2010

  42. [50]

    Discrete Mathematics 173(1):71–78, DOI 10.1016/S0012-365X(96)00097-0

    Ille P (1997) Indecomposable graphs. Discrete Mathematics 173(1):71–78, DOI 10.1016/S0012-365X(96)00097-0

    1997 doi

  43. [51]

    In: Rival I (ed) Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, Springer Netherlands, Dordrecht, pp 3–40, DOI 10.1007/978-94-009-5315-4 1

    Kelly D (1985) Comparability graphs. In: Rival I (ed) Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications, Springer Netherlands, Dordrecht, pp 3–40, DOI 10.1007/978-94-009-5315-4 1

    1985 doi

  44. [52]

    J Math Biol 84(6):47, DOI 10.1007/s00285-022-01746-y

    Kong S, Pons JC, Kubatko L, Wicke K (2022) Classes of explicit phylogenetic networks and their biological and mathematical significance. J Math Biol 84(6):47, DOI 10.1007/s00285-022-01746-y

    2022 doi

  45. [53]

    Briefings in Bioinformatics 12(5):379–391, DOI 10.1093/bib/bbr030

    Kristensen DM, Wolf YI, Mushegian AR, Koonin EV (2011) Computational methods for gene orthology inference. Briefings in Bioinformatics 12(5):379–391, DOI 10.1093/bib/bbr030

    2011 doi

  46. [54]

    TRENDS in Genetics 21(1):25–30, DOI 10.1016/j.tig.2004.11.007

    Kummerfeld SK, Teichmann SA (2005) Relative rates of gene fusion and fission in multi-domain proteins. TRENDS in Genetics 21(1):25–30, DOI 10.1016/j.tig.2004.11.007

    2005 doi

  47. [55]

    Trends in Genetics 24(11):539–551, DOI 10.1016/j.tig.2008.08.009

    Kuzniar A, van Ham RC, Pongor S, Leunissen JA (2008) The quest for orthologs: finding the corresponding gene across genomes. Trends in Genetics 24(11):539–551, DOI 10.1016/j.tig.2008.08.009

    2008 doi

  48. [56]

    Journal of Computer and System Sciences 20(2):219–230, DOI 10.1016/0022-0000(80)90060-4

    Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences 20(2):219–230, DOI 10.1016/0022-0000(80)90060-4

    1980 doi

  49. [57]

    Bulletin of Mathematical Biology 87(3):44, DOI 10.1007/s11538-025-01419-z

    Lindeberg A, Hellmuth M (2025) Simplifying and characterizing DAGs and phylogenetic networks via least com- mon ancestor constraints. Bulletin of Mathematical Biology 87(3):44, DOI 10.1007/s11538-025-01419-z

    2025 doi

  50. [58]

    Vietnam Journal of Mathematics Special Issue dedicated to the memory of Andreas Dress (to appear, preprint arXiv:2406.18713)

    Lindeberg A, Scholz G, Hellmuth M (2024) Network representation and modular decomposition of combinatorial structures: A galled-tree perspective. Vietnam Journal of Mathematics Special Issue dedicated to the memory of Andreas Dress (to appear, preprint arXiv:2406.18713)

    2024 arXiv

  51. [59]

    Journal of Combinatorial Theory, Series B 13(2):95–98, DOI 10.1016/0095-8956(72)90045-7

    Lov ´asz L (1972) A characterization of perfect graphs. Journal of Combinatorial Theory, Series B 13(2):95–98, DOI 10.1016/0095-8956(72)90045-7

    1972 doi

  52. [60]

    Discrete Mathematics 2(3):253–267, DOI 10.1016/0012-365X(72)90006-4

    Lov ´asz L (1972) Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2(3):253–267, DOI 10.1016/0012-365X(72)90006-4

    1972 doi

  53. [61]

    PLOS Computational Biology 18(11):e1010621, DOI 10.1371/journal.pcbi.1010621

    Menet H, Daubin V , Tannier E (2022) Phylogenetic reconciliation. PLOS Computational Biology 18(11):e1010621, DOI 10.1371/journal.pcbi.1010621

    2022 doi

  54. [62]

    Annals of Operations Research 4(1):195–225, DOI 10.1007/BF02022041

    M ¨ohring R (1985) Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research 4(1):195–225, DOI 10.1007/BF02022041

    1985 doi

  55. [63]

    M ¨ohring R, Radermacher F (1984) Substitution decomposition for discrete structures and connections with com- binatorial optimization. In: Burkard R, Cuninghame-Green R, Zimmermann U (eds) Algebraic and Combinatorial Methods in Operations Research, North-Holland Mathematics S...

    1984 doi

  56. [64]

    Nature 431(7005):152–155, DOI 10.1038/nature02848

    Rivera MC, Lake JA (2004) The ring of life provides evidence for a genome fusion origin of eukaryotes. Nature 431(7005):152–155, DOI 10.1038/nature02848

    2004 doi

  57. [65]

    Best Match Graphs

    Schaller D, Geiß M, Ch ´avez E, Gonz ´alez Laffitte M, L ´opez S´anchez A, Stadler BMR, Valdivia DI, Hellmuth M, Hern´andez Rosales M, Stadler PF (2021) Corrigendum to “Best Match Graphs”. J Math Biol 82:47, DOI 10.1007/ s00285-021-01601-6

    2021

  58. [66]

    J Math Biol 82:20, DOI 10.1007/s00285-021-01564-8

    Schaller D, Geiß M, Stadler PF, Hellmuth M (2021) Complete characterization of incorrect orthology assignments in best match graphs. J Math Biol 82:20, DOI 10.1007/s00285-021-01564-8

    2021 doi

  59. [67]

    In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), SIAM, pp 67–77, DOI 10.1137/1.9781611977042.6

    Schidler A, Szeider S (2022) A SAT approach to twin-width. In: 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), SIAM, pp 67–77, DOI 10.1137/1.9781611977042.6

    2022 doi

  60. [68]

    Discrete Mathematics 113(1):191–205, DOI 10.1016/0012-365X(93)90516-V 24

    Schmerl JH, Trotter WT (1993) Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Mathematics 113(1):191–205, DOI 10.1016/0012-365X(93)90516-V 24

    1993 doi

  61. [69]

    Journal of Combinatorial Theory, Series B 16(2):191–193, DOI 10.1016/0095-8956(74)90063-X

    Seinsche D (1974) On a property of the class of n-colorable graphs. Journal of Combinatorial Theory, Series B 16(2):191–193, DOI 10.1016/0095-8956(74)90063-X

    1974 doi

  62. [70]

    Oxford University Press, Oxford, UK

    Semple C, Steel M (2003) Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, vol 24. Oxford University Press, Oxford, UK

    2003

  63. [71]

    In: Kalyanasundaram S, Maheshwari A (eds) Algorithms and Discrete Applied Mathematics, Springer Nature Switzerland, Cham, pp 148–161, DOI 10.1007/978-3-031-52213-0 11

    Shanavas A V , Changat M, Hellmuth M, Stadler PF (2024) Unique least common ancestors and clusters in di- rected acyclic graphs. In: Kalyanasundaram S, Maheshwari A (eds) Algorithms and Discrete Applied Mathematics, Springer Nature Switzerland, Cham, pp 148–161, DOI 10.1007/97...

    2024 doi

  64. [72]

    Systematic biology 63(3):409–420, DOI 10.1093/sysbio/syu007

    Sj ¨ostrand J, Tofigh A, Daubin V , Arvestad L, Sennblad B, Lagergren J (2014) A bayesian method for analyzing lateral gene transfer. Systematic biology 63(3):409–420, DOI 10.1093/sysbio/syu007

    2014 doi

  65. [73]

    Discrete Mathematics 6(3):281–298, DOI 10.1016/0012-365X(73)90100-3

    Sumner DP (1973) Graphs indecomposable with respect to the X-join. Discrete Mathematics 6(3):281–298, DOI 10.1016/0012-365X(73)90100-3

    1973 doi

  66. [74]

    Journal of the Australian Mathematical Society 18(4):492–502, DOI 10.1017/ S1446788700029232

    Sumner DP (1974) Dacey graphs. Journal of the Australian Mathematical Society 18(4):492–502, DOI 10.1017/ S1446788700029232

    1974

  67. [75]

    Science 278(5338):631–637, DOI 10.1126/science.278.5338.631

    Tatusov RL, Koonin EV , Lipman DJ (1997) A genomic perspective on protein families. Science 278(5338):631–637, DOI 10.1126/science.278.5338.631

    1997 doi

  68. [76]

    IEEE/ACM transactions on computational biology and bioinformatics 8(2):517–535, DOI 10.1109/TCBB.2010.14

    Tofigh A, Hallett M, Lagergren J (2010) Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM transactions on computational biology and bioinformatics 8(2):517–535, DOI 10.1109/TCBB.2010.14

    2010 doi

  69. [77]

    Discrete Applied Mathematics 128(2):487– 509, DOI 10.1016/S0166-218X(02)00507-3 25

    Zverovich I (2003) Extension of hereditary classes with substitutions. Discrete Applied Mathematics 128(2):487– 509, DOI 10.1016/S0166-218X(02)00507-3 25

    2003 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.