Carsten R. Seemann
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Carsten R. Seemann has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Marc Hellmuth
Faculty of Mathematics and Computer Science, Leipzig University, Leipzig, Germany
5 shared publications - Peter Florian Stadler
Max Planck Institute for Mathematics in the Sciences
3 shared publications - Fabian Gärtner
Competence Center for Scalable Data Services and Solutions Dresden/Leipzig (scaDS), Universität Leipzig, Augustusplatz 12, D-04107 Leipzig, Germany
2 shared publications Peter F. Stadler
2 shared publicationsChristian Höner zu Siederdissen
1 shared publication- Christian Höner zu Siederdissen
RNA Bioinformatics and High-Throughput Analysis, Friedrich Schiller University , Leutragraben 1 , 07743 Jena
1 shared publication
Latest Publications
- Open Access
- 30 January 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 331, 38-58
Planar median graphs and cubesquare-graphs
- 30 January 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 331, 38-58
Open AccessPlanar median graphs and cubesquare-graphs
- Open Access
- 3 June 2021
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 23 no. 1 (Graph Theo)
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps $\varepsilon$ that assign a subset of colors to each pair of vertices in $X$ and that can be explained by a tree $T$ with edges that are labeled with subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$ if and only if $m$ appears in a label along the unique path between $x$ and $y$ in $T$. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where $|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.- 3 June 2021
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Discrete Mathematics & Theoretical Computer Science
- Vol. 23 no. 1 (Graph Theo)
Open AccessGeneralized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps $\varepsilon$ that assign a subset of colors to each pair of vertices in $X$ and that can be explained by a tree $T$ with edges that are labeled with subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$ if and only if $m$ appears in a label along the unique path between $x$ and $y$ in $T$. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where $|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs. - 1 September 2020
- Published by Cambridge University Press (CUP) in Network Science
- Vol. 9 (1) , 49-58
Superbubbles as an empirical characteristic of directed networks
Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.
- 1 September 2020
- Published by Cambridge University Press (CUP) in Network Science
- Vol. 9 (1) , 49-58
Superbubbles as an empirical characteristic of directed networks
Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.
- 1 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 283, 495-511
Generalized Fitch graphs II: Sets of binary relations that are explained by edge-labeled trees
- 1 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 283, 495-511
Generalized Fitch graphs II: Sets of binary relations that are explained by edge-labeled trees
- Open Access
Superbubbles as an Empirical Characteristic of Directed Networks
Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.
Open AccessSuperbubbles as an Empirical Characteristic of Directed Networks
Superbubbles are acyclic induced subgraphs of a digraph with single entrance and exit that naturally arise in the context of genome assembly and the analysis of genome alignments in computational biology. These structures can be computed in linear time and are confined to non-symmetric digraphs. We demonstrate empirically that graph parameters derived from superbubbles provide a convenient means of distinguishing different classes of real-world graphical models, while being largely unrelated to simple, commonly used parameters.
- 20 May 2019
- Published by Springer Nature in Journal of Mathematical Biology
- Vol. 79 (3) , 969-986
Alternative characterizations of Fitch’s xenology relation
Horizontal gene transfer (HGT) is an important factor for the evolution of prokaryotes as well as eukaryotes. According to Walter M. Fitch, two genes are xenologs if they are separated by at least one HGT. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs (x, y) 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. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. The mathematical characterization of Fitch relations is crucial to understand whether putative xenology relations are at least to some extent “biologically feasible”. In this contribution, we provide two novel characterizations of Fitch relations. In particular, these results allow us directly to reconstruct gene trees (together with the location of the horizontal transfer events) that explain the underlying Fitch relation. As a biological side result, we can conclude that the phylogenetic signal to infer these gene trees is entirely contained in those pairs of genes x and y for which no directional transfer has been taken place in the common history of y and the last common ancestor of x and y. In other words, non-HGT events provide the essential information about the gene trees. In addition, we utilize the new characterizations to present an alternative, short and elegant proof of the characterization theorem established by Geiß et al. (J Math Bio 77(5), 2018).
- 20 May 2019
- Published by Springer Nature in Journal of Mathematical Biology
- Vol. 79 (3) , 969-986
Alternative characterizations of Fitch’s xenology relation
Horizontal gene transfer (HGT) is an important factor for the evolution of prokaryotes as well as eukaryotes. According to Walter M. Fitch, two genes are xenologs if they are separated by at least one HGT. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs (x, y) 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. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. The mathematical characterization of Fitch relations is crucial to understand whether putative xenology relations are at least to some extent “biologically feasible”. In this contribution, we provide two novel characterizations of Fitch relations. In particular, these results allow us directly to reconstruct gene trees (together with the location of the horizontal transfer events) that explain the underlying Fitch relation. As a biological side result, we can conclude that the phylogenetic signal to infer these gene trees is entirely contained in those pairs of genes x and y for which no directional transfer has been taken place in the common history of y and the last common ancestor of x and y. In other words, non-HGT events provide the essential information about the gene trees. In addition, we utilize the new characterizations to present an alternative, short and elegant proof of the characterization theorem established by Geiß et al. (J Math Bio 77(5), 2018).
- Open Access
Alternative Characterizations of Fitch's Xenology Relation
According to Walter M. Fitch, two genes are xenologs if they are separated by at least one horizontal gene transfer. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs $(x,y)$ of genes $x$ and $y$ for which $y$ has been horizontally transferred at least once since it diverged from the least common ancestor of $x$ and $y$. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. In this contribution, we provide two novel characterizations of Fitch relations and present an alternative, short and elegant proof of the characterization theorem established by Gei{\ss} et al.\ in \emph{J.\ Math.\ Bio 77(5), 2018}.Open AccessAlternative Characterizations of Fitch's Xenology Relation
According to Walter M. Fitch, two genes are xenologs if they are separated by at least one horizontal gene transfer. This concept is formalized through Fitch relations, which are defined as binary relations that comprise all pairs $(x,y)$ of genes $x$ and $y$ for which $y$ has been horizontally transferred at least once since it diverged from the least common ancestor of $x$ and $y$. This definition, in particular, preserves the directional character of the transfer. Fitch relations are characterized by a small set of forbidden induced subgraphs on three vertices and can be recognized in linear time. In this contribution, we provide two novel characterizations of Fitch relations and present an alternative, short and elegant proof of the characterization theorem established by Gei{\ss} et al.\ in \emph{J.\ Math.\ Bio 77(5), 2018}. - 30 April 2018
- Published by Elsevier in European Journal of Combinatorics
- Vol. 70, 384-407
The matroid structure of representative triple sets and triple-closure computation
- 30 April 2018
- Published by Elsevier in European Journal of Combinatorics
- Vol. 70, 384-407
The matroid structure of representative triple sets and triple-closure computation