| 1. |
- Chen, Zhishan, et al.
(författare)
-
Fine-mapping analysis including over 254 000 East Asian and European descendants identifies 136 putative colorectal cancer susceptibility genes
- 2024
-
Ingår i: Nature Communications. - : Springer Nature. - 2041-1723. ; 15:1
-
Tidskriftsartikel (refereegranskat)abstract
- Genome-wide association studies (GWAS) have identified more than 200 common genetic variants independently associated with colorectal cancer (CRC) risk, but the causal variants and target genes are mostly unknown. We sought to fine-map all known CRC risk loci using GWAS data from 100,204 cases and 154,587 controls of East Asian and European ancestry. Our stepwise conditional analyses revealed 238 independent association signals of CRC risk, each with a set of credible causal variants (CCVs), of which 28 signals had a single CCV. Our cis-eQTL/mQTL and colocalization analyses using colorectal tissue-specific transcriptome and methylome data separately from 1299 and 321 individuals, along with functional genomic investigation, uncovered 136 putative CRC susceptibility genes, including 56 genes not previously reported. Analyses of single-cell RNA-seq data from colorectal tissues revealed 17 putative CRC susceptibility genes with distinct expression patterns in specific cell types. Analyses of whole exome sequencing data provided additional support for several target genes identified in this study as CRC susceptibility genes. Enrichment analyses of the 136 genes uncover pathways not previously linked to CRC risk. Our study substantially expanded association signals for CRC and provided additional insight into the biological mechanisms underlying CRC development.
|
|
| 2. |
- Fernandez-Rozadilla, Ceres, et al.
(författare)
-
Deciphering colorectal cancer genetics through multi-omic analysis of 100,204 cases and 154,587 controls of European and east Asian ancestries
- 2023
-
Ingår i: Nature Genetics. - : Nature Publishing Group. - 1061-4036 .- 1546-1718. ; 55, s. 89-99
-
Tidskriftsartikel (refereegranskat)abstract
- Colorectal cancer (CRC) is a leading cause of mortality worldwide. We conducted a genome-wide association study meta-analysis of 100,204 CRC cases and 154,587 controls of European and east Asian ancestry, identifying 205 independent risk associations, of which 50 were unreported. We performed integrative genomic, transcriptomic and methylomic analyses across large bowel mucosa and other tissues. Transcriptome- and methylome-wide association studies revealed an additional 53 risk associations. We identified 155 high-confidence effector genes functionally linked to CRC risk, many of which had no previously established role in CRC. These have multiple different functions and specifically indicate that variation in normal colorectal homeostasis, proliferation, cell adhesion, migration, immunity and microbial interactions determines CRC risk. Crosstissue analyses indicated that over a third of effector genes most probably act outside the colonic mucosa. Our findings provide insights into colorectal oncogenesis and highlight potential targets across tissues for new CRC treatment and chemoprevention strategies.
|
|
| 3. |
- Schaller, David, et al.
(författare)
-
Corrigendum to “Best match graphs”
- 2021
-
Ingår i: Journal of Mathematical Biology. - : Springer Science and Business Media LLC. - 0303-6812 .- 1432-1416. ; 82:6
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Two errors in the article Best Match Graphs (Geiß et al. in JMB 78: 2015–2057, 2019) are corrected. One concerns the tacit assumption that digraphs are sink-free, which has to be added as an additional precondition in Lemma 9, Lemma 11, Theorem 4. Correspondingly, Algorithm 2 requires that its input is sink-free. The second correction concerns an additional necessary condition in Theorem 9 required to characterize best match graphs. The amended results simplify the construction of least resolved trees for n-cBMGs, i.e., Algorithm 1. All other results remain unchanged and are correct as stated.
|
|
| 4. |
- Bruckmann, Carmen, et al.
(författare)
-
From modular decomposition trees to rooted median graphs
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 310, s. 1-9
-
Tidskriftsartikel (refereegranskat)abstract
- The modular decomposition of a symmetric map δ:X×X→Υ (or, equivalently, a set of pairwise-disjoint symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of δ in terms of a labeled tree. A map δ is explained by a vertex-labeled rooted tree (T,t) if the label δ(x,y) coincides with the label of the lowest common ancestor of x and y in T, i.e., if δ(x,y)=t(lca(x,y)). Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be explained in this manner. Here we consider rooted median graphs as a generalization of (modular decomposition) trees to explain symmetric maps. We derive a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map δ.
|
|
| 5. |
- Dong, Shuo, et al.
(författare)
-
Observation of ultrafast interfacial Meitner-Auger energy transfer in a Van der Waals heterostructure
- 2023
-
Ingår i: Nature Communications. - : Springer Nature. - 2041-1723. ; 14:1
-
Tidskriftsartikel (refereegranskat)abstract
- Atomically thin layered van der Waals heterostructures feature exotic and emergent optoelectronic properties. With growing interest in these novel quantum materials, the microscopic understanding of fundamental interfacial coupling mechanisms is of capital importance. Here, using multidimensional photoemission spectroscopy, we provide a layer- and momentum-resolved view on ultrafast interlayer electron and energy transfer in a monolayer-WSe2/graphene heterostructure. Depending on the nature of the optically prepared state, we find the different dominating transfer mechanisms: while electron injection from graphene to WSe2 is observed after photoexcitation of quasi-free hot carriers in the graphene layer, we establish an interfacial Meitner-Auger energy transfer process following the excitation of excitons in WSe2. By analysing the time-energy-momentum distributions of excited-state carriers with a rate-equation model, we distinguish these two types of interfacial dynamics and identify the ultrafast conversion of excitons in WSe2 to valence band transitions in graphene. Microscopic calculations find interfacial dipole-monopole coupling underlying the Meitner-Auger energy transfer to dominate over conventional Förster- and Dexter-type interactions, in agreement with the experimental observations. The energy transfer mechanism revealed here might enable new hot-carrier-based device concepts with van der Waals heterostructures.
|
|
| 6. |
- Hellmuth, Marc, 1980-, et al.
(författare)
-
Clustering systems of phylogenetic networks
- 2023
-
Ingår i: Theory in biosciences. - 1431-7613 .- 1611-7530. ; :142, s. 301-358
-
Tidskriftsartikel (refereegranskat)abstract
- Rooted acyclic graphs appear naturally when the phylogenetic relationship of a set X of taxa involves not only speciations but also recombination, horizontal transfer, or hybridization that cannot be captured by trees. A variety of classes of such networks have been discussed in the literature, including phylogenetic, level-1, tree-child, tree-based, galled tree, regular, or normal networks as models of different types of evolutionary processes. Clusters arise in models of phylogeny as the sets C(v) of descendant taxa of a vertex v. The clustering system CN comprising the clusters of a network N conveys key information on N itself. In the special case of rooted phylogenetic trees, T is uniquely determined by its clustering system CT. Although this is no longer true for networks in general, it is of interest to relate properties of N and CN. Here, we systematically investigate the relationships of several well-studied classes of networks and their clustering systems. The main results are correspondences of classes of networks and clustering systems of the following form: If N is a network of type X, then CN satisfies Y, and conversely if C is a clustering system satisfying Y, then there is network N of type X such that C⊆CN.This, in turn, allows us to investigate the mutual dependencies between the distinct types of networks in much detail.
|
|
| 7. |
- Hellmuth, Marc, et al.
(författare)
-
Combining Orthology and Xenology Data in a Common Phylogenetic Tree
- 2021
-
Ingår i: Advances in Bioinformatics and Computational Biology. - Cham : Springer. - 9783030918132 - 9783030918149 ; , s. 53-64
-
Konferensbidrag (refereegranskat)abstract
- In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels λ(e). The orthology and paralogy relations between genes are a special case of a map δ on the pairs of leaves of T defined by δ(x,y)=q if the last common ancestor lca(x,y) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map εε with m∈ε(x,y) if m∈λ(e) for at least one edge e along the path from lca(x,y) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps (δ,ε) derives from a tree (T,t,λ) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (Tδ,tδ) that explains δ and the (unique) least-resolved edge labeled tree (Tε,λε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.
|
|
| 8. |
- Hellmuth, Marc, et al.
(författare)
-
Compatibility of partitions with trees, hierarchies, and split systems
- 2022
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 314, s. 265-283
-
Tidskriftsartikel (refereegranskat)abstract
- The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T∗ of T exists such that T∗ and P are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with P. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps.
|
|
| 9. |
- Hellmuth, Marc, et al.
(författare)
-
Fitch Graph Completion
- 2023
-
Ingår i: Lecture Notes in Computer Science. - 0302-9743 .- 1611-3349. ; , s. 225-237
-
Tidskriftsartikel (refereegranskat)
|
|
| 10. |
- Hellmuth, Marc, et al.
(författare)
-
Generalized Fitch Graphs III : Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
- 2021
-
Ingår i: Discrete Mathematics & Theoretical Computer Science. - : Centre pour la Communication Scientifique Directe (CCSD). - 1462-7264 .- 1365-8050. ; 23:1
-
Tidskriftsartikel (refereegranskat)abstract
- 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 epsilon 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 epsilon(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 vertical bar epsilon(x, y)vertical bar <= 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.
|
|
| 11. |
- Hyde, K. D., et al.
(författare)
-
Global consortium for the classification of fungi and fungus-like taxa
- 2023
-
Ingår i: MYCOSPHERE. - : Mushroom Research Foundation. - 2077-7000 .- 2077-7019. ; 14:1, s. 1960-2012
-
Tidskriftsartikel (refereegranskat)abstract
- The Global Consortium for the Classification of Fungi and fungus-like taxa is an international initiative of more than 550 mycologists to develop an electronic structure for the classification of these organisms. The members of the Consortium originate from 55 countries/regions worldwide, from a wide range of disciplines, and include senior, mid-career and early-career mycologists and plant pathologists. The Consortium will publish a biannual update of the Outline of Fungi and fungus-like taxa, to act as an international scheme for other scientists. Notes on all newly published taxa at or above the level of species will be prepared and published online on the Outline of Fungi website (https://www.outlineoffungi.org/), and these will be finally published in the biannual edition of the Outline of Fungi and fungus-like taxa. Comments on recent important taxonomic opinions on controversial topics will be included in the biannual outline. For example, 'to promote a more stable taxonomy in Fusarium given the divergences over its generic delimitation', or 'are there too many genera in the Boletales?' and even more importantly, 'what should be done with the tremendously diverse 'dark fungal taxa?' There are undeniable differences in mycologists' perceptions and opinions regarding species classification as well as the establishment of new species. Given the pluralistic nature of fungal taxonomy and its implications for species concepts and the nature of species, this consortium aims to provide a platform to better refine and stabilise fungal classification, taking into consideration views from different parties. In the future, a confidential voting system will be set up to gauge the opinions of all mycologists in the Consortium on important topics. The results of such surveys will be presented to the International Commission on the Taxonomy of Fungi (ICTF) and the Nomenclature Committee for Fungi (NCF) with opinions and percentages of votes for and against. Criticisms based on scientific evidence with regards to nomenclature, classifications, and taxonomic concepts will be welcomed, and any recommendations on specific taxonomic issues will also be encouraged; however, we will encourage professionally and ethically responsible criticisms of others' work. This biannual ongoing project will provide an outlet for advances in various topics of fungal classification, nomenclature, and taxonomic concepts and lead to a community-agreed classification scheme for the fungi and fungus-like taxa. Interested parties should contact the lead author if they would like to be involved in future outlines.
|
|
| 12. |
- Korchmaros, Annachiara, et al.
(författare)
-
Quasi-best match graphs
- 2023
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 331, s. 104-125
-
Tidskriftsartikel (refereegranskat)abstract
- Quasi-best match graphs (qBMGs) are a hereditary class of directed, properly vertex -colored graphs. They arise naturally in mathematical phylogenetics as a generalization of best match graphs, which formalize the notion of evolutionary closest relatedness of genes (vertices) in multiple species (vertex colors). They are explained by rooted trees whose leaves correspond to vertices. In contrast to BMGs, qBMGs represent only best matches at a restricted phylogenetic distance. We provide characterizations of qBMGs that give rise to polynomial-time recognition algorithms and identify the BMGs as the qBMGs that are color-sink-free. Furthermore, two-colored qBMGs are characterized as directed graphs satisfying three simple local conditions, two of which have appeared previously, namely bi-transitivity in the sense of Das et al. (2021) and a hierarchy-like structure of out-neighborhoods, i.e., N(x) n N(y) E {N(x), N(y), 0} for any two vertices x and y. Further results characterize qBMGs that can be explained by binary phylogenetic trees.
|
|
| 13. |
- Mahdessian, Diana, et al.
(författare)
-
Spatiotemporal dissection of the cell cycle with single-cell proteogenomics
- 2021
-
Ingår i: Nature. - : Springer Nature. - 0028-0836 .- 1476-4687. ; 590:7847
-
Tidskriftsartikel (refereegranskat)abstract
- Spatial and temporal variations among individual human cell proteomes are comprehensively mapped across the cell cycle using proteomic imaging and transcriptomics. The cell cycle, over which cells grow and divide, is a fundamental process of life. Its dysregulation has devastating consequences, including cancer(1-3). The cell cycle is driven by precise regulation of proteins in time and space, which creates variability between individual proliferating cells. To our knowledge, no systematic investigations of such cell-to-cell proteomic variability exist. Here we present a comprehensive, spatiotemporal map of human proteomic heterogeneity by integrating proteomics at subcellular resolution with single-cell transcriptomics and precise temporal measurements of individual cells in the cell cycle. We show that around one-fifth of the human proteome displays cell-to-cell variability, identify hundreds of proteins with previously unknown associations with mitosis and the cell cycle, and provide evidence that several of these proteins have oncogenic functions. Our results show that cell cycle progression explains less than half of all cell-to-cell variability, and that most cycling proteins are regulated post-translationally, rather than by transcriptomic cycling. These proteins are disproportionately phosphorylated by kinases that regulate cell fate, whereas non-cycling proteins that vary between cells are more likely to be modified by kinases that regulate metabolism. This spatially resolved proteomic map of the cell cycle is integrated into the Human Protein Atlas and will serve as a resource for accelerating molecular studies of the human cell cycle and cell proliferation.
|
|
| 14. |
- Miethke, Marcus, et al.
(författare)
-
Towards the sustainable discovery and development of new antibiotics
- 2021
-
Ingår i: Nature Reviews Chemistry. - : Springer Nature. - 2397-3358. ; 5:10, s. 726-749
-
Forskningsöversikt (refereegranskat)abstract
- An ever-increasing demand for novel antimicrobials to treat life-threatening infections caused by the global spread of multidrug-resistant bacterial pathogens stands in stark contrast to the current level of investment in their development, particularly in the fields of natural-product-derived and synthetic small molecules. New agents displaying innovative chemistry and modes of action are desperately needed worldwide to tackle the public health menace posed by antimicrobial resistance. Here, our consortium presents a strategic blueprint to substantially improve our ability to discover and develop new antibiotics. We propose both short-term and long-term solutions to overcome the most urgent limitations in the various sectors of research and funding, aiming to bridge the gap between academic, industrial and political stakeholders, and to unite interdisciplinary expertise in order to efficiently fuel the translational pipeline for the benefit of future generations.
|
|
| 15. |
- Nounu, Aayah, et al.
(författare)
-
A combined proteomics and mendelian randomization approach to investigate the effects of aspirin-targeted proteins on colorectal cancer
- 2021
-
Ingår i: Cancer Epidemiology, Biomarkers and Prevention. - : Elsevier. - 1055-9965 .- 1538-7755. ; 30:3, s. 564-575
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Evidence for aspirin’s chemopreventative properties on colorectal cancer (CRC) is substantial, but its mechanism of action is not well-understood. We combined a proteomic approach with Mendelian randomization (MR) to identify possible new aspirin targets that decrease CRC risk.Methods: Human colorectal adenoma cells (RG/C2) were treated with aspirin (24 hours) and a stable isotope labeling with amino acids in cell culture (SILAC) based proteomics approach identified altered protein expression. Protein quantitative trait loci (pQTLs) from INTERVAL (N ¼ 3,301) and expression QTLs (eQTLs) from the eQTLGen Consortium (N ¼ 31,684) were used as genetic proxies for protein and mRNA expression levels. Two-sample MR of mRNA/protein expression on CRC risk was performed using eQTL/pQTL data combined with CRC genetic summary data from the Colon Cancer Family Registry (CCFR), Colorectal Transdisciplinary (CORECT), Genetics and Epidemiology of Colorectal Cancer (GECCO) consortia and UK Biobank (55,168 cases and 65,160 controls).Results: Altered expression was detected for 125/5886 proteins. Of these, aspirin decreased MCM6, RRM2, and ARFIP2 expression, and MR analysis showed that a standard deviation increase in mRNA/protein expression was associated with increased CRC risk (OR: 1.08, 95% CI, 1.03–1.13; OR: 3.33, 95% CI, 2.46–4.50; and OR: 1.15, 95% CI, 1.02–1.29, respectively).Conclusions: MCM6 and RRM2 are involved in DNA repair whereby reduced expression may lead to increased DNA aberrations and ultimately cancer cell death, whereas ARFIP2 is involved in actin cytoskeletal regulation, indicating a possible role in aspirin’s reduction of metastasis.Impact: Our approach has shown how laboratory experiments and population-based approaches can combine to identify aspirin-targeted proteins possibly affecting CRC risk.
|
|
| 16. |
- Nounu, Aayah, et al.
(författare)
-
Salicylic Acid and Risk of Colorectal Cancer : A Two-Sample Mendelian Randomization Study
- 2021
-
Ingår i: Nutrients. - : MDPI. - 2072-6643. ; 13:11
-
Tidskriftsartikel (refereegranskat)abstract
- Salicylic acid (SA) has observationally been shown to decrease colorectal cancer (CRC) risk. Aspirin (acetylsalicylic acid, that rapidly deacetylates to SA) is an effective primary and secondary chemopreventive agent. Through a Mendelian randomization (MR) approach, we aimed to address whether levels of SA affected CRC risk, stratifying by aspirin use. A two-sample MR analysis was performed using GWAS summary statistics of SA (INTERVAL and EPIC-Norfolk, N = 14,149) and CRC (CCFR, CORECT, GECCO and UK Biobank, 55,168 cases and 65,160 controls). The DACHS study (4410 cases and 3441 controls) was used for replication and stratification of aspirin-use. SNPs proxying SA were selected via three methods: (1) functional SNPs that influence the activity of aspirin-metabolising enzymes; (2) pathway SNPs present in enzymes' coding regions; and (3) genome-wide significant SNPs. We found no association between functional SNPs and SA levels. The pathway and genome-wide SNPs showed no association between SA and CRC risk (OR: 1.03, 95% CI: 0.84-1.27 and OR: 1.08, 95% CI: 0.86-1.34, respectively). Results remained unchanged upon aspirin use stratification. We found little evidence to suggest that an SD increase in genetically predicted SA protects against CRC risk in the general population and upon stratification by aspirin use.
|
|
| 17. |
- Schaller, David, et al.
(författare)
-
A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set
- 2021
-
Ingår i: Algorithms for Molecular Biology. - : Springer Science and Business Media LLC. - 1748-7188. ; 16
-
Tidskriftsartikel (refereegranskat)abstract
- Background: The supertree problem, i.e., the task of finding a common refinement of a set of rooted trees is an important topic in mathematical phylogenetics. The special case of a common leaf set L is known to be solvable in linear time. Existing approaches refine one input tree using information of the others and then test whether the results are isomorphic.Results: An O(k|L|) algorithm, LinCR, for constructing the common refinement T of k input trees with a common leaf set L is proposed that explicitly computes the parent function of T in a bottom-up approach.Conclusion: LinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons.
|
|
| 18. |
- Schaller, David, et al.
(författare)
-
Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
- 2021
-
Ingår i: Algorithms. - : MDPI AG. - 1999-4893. ; 14:4
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.
|
|
| 19. |
- Schaller, David, et al.
(författare)
-
Best Match Graphs with Binary Trees
- 2021
-
Ingår i: Algorithms for Computational Biology. - Cham : Springer. - 9783030744311 - 9783030744328 ; , s. 82-93
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 20. |
- Schaller, David, et al.
(författare)
-
Best Match Graphs With Binary Trees
- 2023
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 20:3, s. 1679-1690
-
Tidskriftsartikel (refereegranskat)abstract
- 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 is binary-explainable, i.e., whether it 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-refinable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.
|
|
| 21. |
- Schaller, David, et al.
(författare)
-
Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs
- 2021
-
Ingår i: Journal of Mathematical Biology. - : Springer Science and Business Media LLC. - 0303-6812 .- 1432-1416. ; 82:20
-
Tidskriftsartikel (refereegranskat)abstract
- Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least 75% of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.
|
|
| 22. |
- Schaller, David, et al.
(författare)
-
Complexity of modification problems for best match graphs
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975 .- 1879-2294. ; 865, s. 63-84
-
Tidskriftsartikel (refereegranskat)abstract
- Best match graphs (BMGs) are vertex-colored directed graphs that were introduced to model the relationships of genes (vertices) from different species (colors) given an underlying evolutionary tree that is assumed to be unknown. In real-life applications, BMGs are estimated from sequence similarity data. Measurement noise and approximation errors usually result in empirically determined graphs that in general violate characteristic properties of BMGs. The arc modification problems for BMGs aim at correcting such violations and thus provide a means to improve the initial estimates of best match data. We show here that the arc deletion, arc completion and arc editing problems for BMGs are NP-complete and that they can be formulated and solved as integer linear programs. To this end, we provide a novel characterization of BMGs in terms of triples (binary trees on three leaves) and a characterization of BMGs with two colors in terms of forbidden subgraphs.
|
|
| 23. |
- Schaller, David, et al.
(författare)
-
Heuristic algorithms for best match graph editing
- 2021
-
Ingår i: Algorithms for Molecular Biology. - : Springer Science and Business Media LLC. - 1748-7188. ; 16:1
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Best match graphs (BMGs) are a class of colored digraphs that naturally appear in mathematical phylogenetics as a representation of the pairwise most closely related genes among multiple species. An arc connects a gene x with a gene y from another species (vertex color) Y whenever it is one of the phylogenetically closest relatives of x. BMGs can be approximated with the help of similarity measures between gene sequences, albeit not without errors. Empirical estimates thus will usually violate the theoretical properties of BMGs. The corresponding graph editing problem can be used to guide error correction for best match data. Since the arc set modification problems for BMGs are NP-complete, efficient heuristics are needed if BMGs are to be used for the practical analysis of biological sequence data.Results: Since BMGs have a characterization in terms of consistency of a certain set of rooted triples (binary trees on three vertices) defined on the set of genes, we consider heuristics that operate on triple sets. As an alternative, we show that there is a close connection to a set partitioning problem that leads to a class of top-down recursive algorithms that are similar to Aho’s supertree algorithm and give rise to BMG editing algorithms that are consistent in the sense that they leave BMGs invariant. Extensive benchmarking shows that community detection algorithms for the partitioning steps perform best for BMG editing.Conclusion: Noisy BMG data can be corrected with sufficient accuracy and efficiency to make BMGs an attractive alternative to classical phylogenetic methods.
|
|
| 24. |
- Schaller, David, et al.
(författare)
-
Indirect identification of horizontal gene transfer
- 2021
-
Ingår i: Journal of Mathematical Biology. - : Springer Science and Business Media LLC. - 0303-6812 .- 1432-1416. ; 83:1
-
Tidskriftsartikel (refereegranskat)abstract
- Several implicit methods to infer horizontal gene transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside. This situation defines the edge set of a graph, the later-divergence-time (LDT) graph, whose vertices correspond to genes colored by their species. We investigate these graphs in the setting of relaxed scenarios, i.e., evolutionary scenarios that encompass all commonly used variants of duplication-transfer-loss scenarios in the literature. We characterize LDT graphs as a subclass of properly vertex-colored cographs, and provide a polynomial-time recognition algorithm as well as an algorithm to construct a relaxed scenario that explains a given LDT. An edge in an LDT graph implies that the two corresponding genes are separated by at least one HGT event. The converse is not true, however. We show that the complete xenology relation is described by an rs-Fitch graph, i.e., a complete multipartite graph satisfying constraints on the vertex coloring. This class of vertex-colored graphs is also recognizable in polynomial time. We finally address the question “how much information about all HGT events is contained in LDT graphs” with the help of simulations of evolutionary scenarios with a wide range of duplication, loss, and HGT events. In particular, we show that a simple greedy graph editing scheme can be used to efficiently detect HGT events that are implicitly contained in LDT graphs.
|
|
| 25. |
- Schaller, David, et al.
(författare)
-
Least resolved trees for two-colored best match graphs
- 2021
-
Ingår i: Journal of Graph Algorithms and Applications. - : Journal of Graph Algorithms and Applications. - 1526-1719. ; 25:1, s. 397-416
-
Tidskriftsartikel (refereegranskat)abstract
- In phylogenetic combinatorics, 2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive digraphs that describe the most closely related genes between a pair of species in an evolutionary scenario. They are explained by a unique least resolved tree (LRT). In this paper, the concept of support vertices is introduced and used to derive an O(|V|+|E|log2|V|)-time algorithm that recognizes a 2-BMG and constructs its LRT. The approach can be extended to allow the recognition of binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.
|
|
| 26. |
- Schaller, David, et al.
(författare)
-
Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
- 2023
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801 .- 1095-7146. ; 37:3, s. 2172-2207
-
Tidskriftsartikel (refereegranskat)abstract
- Horizontal gene transfer (HGT) events partition a gene tree T, and thus its leaf set X, into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Two genes thus are xenologs if and only if they belong to two different sets of this partition P. Indirect phylogenetic methods can be used to infer the partition P of X from sequence similarity or evolutionary distances without any a priori knowledge about the underlying tree T. In this contribution, we assume that a partition P of the gene set X and a usually incompletely resolved estimate T of the original gene tree on X are known. We then ask to what extent T and P can be combined to determine the horizontal transfer edges in T and thus the orientation of the HGT events that separate the sets of P. If T and P are compatible, it can be decided for each pair of genes x and y whether there always exists or never exists a horizontal gene transfer in T along the path connecting y and the most recent common ancestor of x and y, and thus a directed edge (x, y) in the so-called Fitch graph of the gene family. We generalize this result to insufficiently resolved gene trees. We show that the classification of a gene pair (x, y) can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree T can be recovered unambiguously from the knowledge of the partition P. All algorithms developed here are implemented and freely available within the Python package AsymmeTree hosted at https://github.com/david-schaller/AsymmeTree.
|
|
| 27. |
- Schaller, David, et al.
(författare)
-
Relative timing information and orthology in evolutionary scenarios
- 2023
-
Ingår i: Algorithms for Molecular Biology. - 1748-7188. ; 18:1
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S. The relative timing of the last common ancestors of two extant genes (leaves of T) and the last common ancestors of the two species (leaves of S) in which they reside is indicative of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene pairs, on the other hand, require that their last common ancestors coincides with a corresponding speciation event. The relative timing information of gene and species divergences is captured by three colored graphs that have the extant genes as vertices and the species in which the genes are found as vertex colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT) graph and the prior-divergence-time (PDT) graph, which together form an edge partition of the complete graph.ResultsHere we give a complete characterization in terms of informative and forbidden triples that can be read off the three graphs and provide a polynomial time algorithm for constructing an evolutionary scenario that explains the graphs, provided such a scenario exists. While both LDT and PDT graphs are cographs, this is not true for the EDT graph in general. We show that every EDT graph is perfect. While the information about LDT and PDT graphs is necessary to recognize EDT graphs in polynomial-time for general scenarios, this extra information can be dropped in the HGT-free case. However, recognition of EDT graphs without knowledge of putative LDT and PDT graphs is NP-complete for general scenarios. In contrast, PDT graphs can be recognized in polynomial-time. We finally connect the EDT graph to the alternative definitions of orthology that have been proposed for scenarios with horizontal gene transfer. With one exception, the corresponding graphs are shown to be colored cographs.
|
|
| 28. |
- Seemann, Carsten R., et al.
(författare)
-
Planar median graphs and cubesquare-graphs
- 2023
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 331, s. 38-58
-
Tidskriftsartikel (refereegranskat)abstract
- Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G, and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square -graphs by a sequence of square-boundaryamalgamations. These considerations also lead to an O(n log n)-time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs.
|
|
| 29. |
- Thomas, Minta, et al.
(författare)
-
Combining Asian and European genome-wide association studies of colorectal cancer improves risk prediction across racial and ethnic populations
- 2023
-
Ingår i: Nature Communications. - : Springer Nature. - 2041-1723. ; 14:1
-
Tidskriftsartikel (refereegranskat)abstract
- Polygenic risk scores (PRS) have great potential to guide precision colorectal cancer (CRC) prevention by identifying those at higher risk to undertake targeted screening. However, current PRS using European ancestry data have sub-optimal performance in non-European ancestry populations, limiting their utility among these populations. Towards addressing this deficiency, we expand PRS development for CRC by incorporating Asian ancestry data (21,731 cases; 47,444 controls) into European ancestry training datasets (78,473 cases; 107,143 controls). The AUC estimates (95% CI) of PRS are 0.63(0.62-0.64), 0.59(0.57-0.61), 0.62(0.60-0.63), and 0.65(0.63-0.66) in independent datasets including 1681-3651 cases and 8696-115,105 controls of Asian, Black/African American, Latinx/Hispanic, and non-Hispanic White, respectively. They are significantly better than the European-centric PRS in all four major US racial and ethnic groups (p-values < 0.05). Further inclusion of non-European ancestry populations, especially Black/African American and Latinx/Hispanic, is needed to improve the risk prediction and enhance equity in applying PRS in clinical practice.
|
|
| 30. |
- Valdivia, Dulce I., et al.
(författare)
-
Hierarchical and modularly-minimal vertex colorings
- 2022
-
Ingår i: The Art of Discrete and Applied Mathematics. - : University of Primorska Press. - 2590-9770. ; 6:2, s. #P2.01-#P2.01
-
Tidskriftsartikel (refereegranskat)
|
|
| 31. |
- Vromman, Marieke, et al.
(författare)
-
Large-scale benchmarking of circRNA detection tools reveals large differences in sensitivity but not in precision
- 2023
-
Ingår i: Nature Methods. - 1548-7091 .- 1548-7105. ; 20:8, s. 1159-1169
-
Tidskriftsartikel (refereegranskat)abstract
- The detection of circular RNA molecules (circRNAs) is typically based on short-read RNA sequencing data processed using computational tools. Numerous such tools have been developed, but a systematic comparison with orthogonal validation is missing. Here, we set up a circRNA detection tool benchmarking study, in which 16 tools detected more than 315,000 unique circRNAs in three deeply sequenced human cell types. Next, 1,516 predicted circRNAs were validated using three orthogonal methods. Generally, tool-specific precision is high and similar (median of 98.8%, 96.3% and 95.5% for qPCR, RNase R and amplicon sequencing, respectively) whereas the sensitivity and number of predicted circRNAs (ranging from 1,372 to 58,032) are the most significant differentiators. Of note, precision values are lower when evaluating low-abundance circRNAs. We also show that the tools can be used complementarily to increase detection sensitivity. Finally, we offer recommendations for future circRNA detection and validation. This study describes benchmarking and validation of computational tools for detecting circRNAs, finding most to be highly precise with variations in sensitivity and total detection. The study also finds over 315,000 putative human circRNAs.
|
|
