| 1. |
- Birney, Ewan, et al.
(författare)
-
Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project
- 2007
-
Ingår i: Nature. - : Springer Science and Business Media LLC. - 0028-0836 .- 1476-4687. ; 447:7146, s. 799-816
-
Tidskriftsartikel (refereegranskat)abstract
- We report the generation and analysis of functional data from multiple, diverse experiments performed on a targeted 1% of the human genome as part of the pilot phase of the ENCODE Project. These data have been further integrated and augmented by a number of evolutionary and computational analyses. Together, our results advance the collective knowledge about human genome function in several major areas. First, our studies provide convincing evidence that the genome is pervasively transcribed, such that the majority of its bases can be found in primary transcripts, including non-protein-coding transcripts, and those that extensively overlap one another. Second, systematic examination of transcriptional regulation has yielded new understanding about transcription start sites, including their relationship to specific regulatory sequences and features of chromatin accessibility and histone modification. Third, a more sophisticated view of chromatin structure has emerged, including its inter-relationship with DNA replication and transcriptional regulation. Finally, integration of these new sources of information, in particular with respect to mammalian evolution based on inter- and intra-species sequence comparisons, has yielded new mechanistic and evolutionary insights concerning the functional landscape of the human genome. Together, these studies are defining a path for pursuit of a more comprehensive characterization of human genome function.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Braasch, Ingo, et al.
(författare)
-
The spotted gar genome illuminates vertebrate evolution and facilitates human-teleost comparisons
- 2016
-
Ingår i: Nature Genetics. - : Springer Science and Business Media LLC. - 1061-4036 .- 1546-1718. ; 48:4, s. 427-437
-
Tidskriftsartikel (refereegranskat)abstract
- To connect human biology to fish biomedical models, we sequenced the genome of spotted gar (Lepisosteus oculatus), whose lineage diverged from teleosts before teleost genome duplication (TGD). The slowly evolving gar genome has conserved in content and size many entire chromosomes from bony vertebrate ancestors. Gar bridges teleosts to tetrapods by illuminating the evolution of immunity, mineralization and development (mediated, for example, by Hox, ParaHox and microRNA genes). Numerous conserved noncoding elements (CNEs; often cis regulatory) undetectable in direct human-teleost comparisons become apparent using gar: functional studies uncovered conserved roles for such cryptic CNEs, facilitating annotation of sequences identified in human genome-wide association studies. Transcriptomic analyses showed that the sums of expression domains and expression levels for duplicated teleost genes often approximate the patterns and levels of expression for gar genes, consistent with subfunctionalization. The gar genome provides a resource for understanding evolution after genome duplication, the origin of vertebrate genomes and the function of human regulatory sequences.
|
|
| 5. |
- Amemiya, Chris T., et al.
(författare)
-
The African coelacanth genome provides insights into tetrapod evolution
- 2013
-
Ingår i: Nature. - : Springer Science and Business Media LLC. - 0028-0836 .- 1476-4687. ; 496:7445, s. 311-316
-
Tidskriftsartikel (refereegranskat)abstract
- The discovery of a living coelacanth specimen in 1938 was remarkable, as this lineage of lobe-finned fish was thought to have become extinct 70 million years ago. The modern coelacanth looks remarkably similar to many of its ancient relatives, and its evolutionary proximity to our own fish ancestors provides a glimpse of the fish that first walked on land. Here we report the genome sequence of the African coelacanth, Latimeria chalumnae. Through a phylogenomic analysis, we conclude that the lungfish, and not the coelacanth, is the closest living relative of tetrapods. Coelacanth protein-coding genes are significantly more slowly evolving than those of tetrapods, unlike other genomic features. Analyses of changes in genes and regulatory elements during the vertebrate adaptation to land highlight genes involved in immunity, nitrogen excretion and the development of fins, tail, ear, eye, brain and olfaction. Functional assays of enhancers involved in the fin-to-limb transition and in the emergence of extra-embryonic tissues show the importance of the coelacanth genome as a blueprint for understanding tetrapod evolution.
|
|
| 6. |
- Huyghe, Jeroen R., et al.
(författare)
-
Discovery of common and rare genetic risk variants for colorectal cancer
- 2019
-
Ingår i: Nature Genetics. - : Nature Publishing Group. - 1061-4036 .- 1546-1718. ; 51:1, s. 76-
-
Tidskriftsartikel (refereegranskat)abstract
- To further dissect the genetic architecture of colorectal cancer (CRC), we performed whole-genome sequencing of 1,439 cases and 720 controls, imputed discovered sequence variants and Haplotype Reference Consortium panel variants into genome-wide association study data, and tested for association in 34,869 cases and 29,051 controls. Findings were followed up in an additional 23,262 cases and 38,296 controls. We discovered a strongly protective 0.3% frequency variant signal at CHD1. In a combined meta-analysis of 125,478 individuals, we identified 40 new independent signals at P < 5 x 10(-8), bringing the number of known independent signals for CRC to similar to 100. New signals implicate lower-frequency variants, Kruppel-like factors, Hedgehog signaling, Hippo-YAP signaling, long noncoding RNAs and somatic drivers, and support a role for immune function. Heritability analyses suggest that CRC risk is highly polygenic, and larger, more comprehensive studies enabling rare variant analysis will improve understanding of biology underlying this risk and influence personalized screening strategies and drug development.
|
|
| 7. |
- 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.
|
|
| 8. |
- Thul, Peter J., et al.
(författare)
-
A subcellular map of the human proteome
- 2017
-
Ingår i: Science. - : American Association for the Advancement of Science. - 0036-8075 .- 1095-9203. ; 356:6340
-
Tidskriftsartikel (refereegranskat)abstract
- Resolving the spatial distribution of the human proteome at a subcellular level can greatly increase our understanding of human biology and disease. Here we present a comprehensive image-based map of subcellular protein distribution, the Cell Atlas, built by integrating transcriptomics and antibody-based immunofluorescence microscopy with validation by mass spectrometry. Mapping the in situ localization of 12,003 human proteins at a single-cell level to 30 subcellular structures enabled the definition of the proteomes of 13 major organelles. Exploration of the proteomes revealed single-cell variations in abundance or spatial distribution and localization of about half of the proteins to multiple compartments. This subcellular map can be used to refine existing protein-protein interaction networks and provides an important resource to deconvolute the highly complex architecture of the human cell.
|
|
| 9. |
- Uhlén, Mathias, et al.
(författare)
-
The human secretome
- 2019
-
Ingår i: Science Signaling. - : American Association for the Advancement of Science (AAAS). - 1945-0877 .- 1937-9145. ; 12:609
-
Tidskriftsartikel (refereegranskat)abstract
- The proteins secreted by human cells (collectively referred to as the secretome) are important not only for the basic understanding of human biology but also for the identification of potential targets for future diagnostics and therapies. Here, we present a comprehensive analysis of proteins predicted to be secreted in human cells, which provides information about their final localization in the human body, including the proteins actively secreted to peripheral blood. The analysis suggests that a large number of the proteins of the secretome are not secreted out of the cell, but instead are retained intracellularly, whereas another large group of proteins were identified that are predicted to be retained locally at the tissue of expression and not secreted into the blood. Proteins detected in the human blood by mass spectrometry-based proteomics and antibody-based immuno-assays are also presented with estimates of their concentrations in the blood. The results are presented in an updated version 19 of the Human Protein Atlas in which each gene encoding a secretome protein is annotated to provide an open-access knowledge resource of the human secretome, including body-wide expression data, spatial localization data down to the single-cell and subcellular levels, and data about the presence of proteins that are detectable in the blood.
|
|
| 10. |
- Zamora, Juan Carlos, et al.
(författare)
-
Considerations and consequences of allowing DNA sequence data as types of fungal taxa
- 2018
-
Ingår i: IMA Fungus. - : INT MYCOLOGICAL ASSOC. - 2210-6340 .- 2210-6359. ; 9:1, s. 167-185
-
Tidskriftsartikel (refereegranskat)abstract
- Nomenclatural type definitions are one of the most important concepts in biological nomenclature. Being physical objects that can be re-studied by other researchers, types permanently link taxonomy (an artificial agreement to classify biological diversity) with nomenclature (an artificial agreement to name biological diversity). Two proposals to amend the International Code of Nomenclature for algae, fungi, and plants (ICN), allowing DNA sequences alone (of any region and extent) to serve as types of taxon names for voucherless fungi (mainly putative taxa from environmental DNA sequences), have been submitted to be voted on at the 11th International Mycological Congress (Puerto Rico, July 2018). We consider various genetic processes affecting the distribution of alleles among taxa and find that alleles may not consistently and uniquely represent the species within which they are contained. Should the proposals be accepted, the meaning of nomenclatural types would change in a fundamental way from physical objects as sources of data to the data themselves. Such changes are conducive to irreproducible science, the potential typification on artefactual data, and massive creation of names with low information content, ultimately causing nomenclatural instability and unnecessary work for future researchers that would stall future explorations of fungal diversity. We conclude that the acceptance of DNA sequences alone as types of names of taxa, under the terms used in the current proposals, is unnecessary and would not solve the problem of naming putative taxa known only from DNA sequences in a scientifically defensible way. As an alternative, we highlight the use of formulas for naming putative taxa (candidate taxa) that do not require any modification of the ICN.
|
|
| 11. |
- Bateman, Alex, et al.
(författare)
-
RNAcentral: A vision for an international database of RNA sequences.
- 2011
-
Ingår i: RNA (New York, N.Y.). - : Cold Spring Harbor Laboratory. - 1469-9001 .- 1355-8382. ; 17:11, s. 1941-6
-
Tidskriftsartikel (refereegranskat)abstract
- During the last decade there has been a great increase in the number of noncoding RNA genes identified, including new classes such as microRNAs and piRNAs. There is also a large growth in the amount of experimental characterization of these RNA components. Despite this growth in information, it is still difficult for researchers to access RNA data, because key data resources for noncoding RNAs have not yet been created. The most pressing omission is the lack of a comprehensive RNA sequence database, much like UniProt, which provides a comprehensive set of protein knowledge. In this article we propose the creation of a new open public resource that we term RNAcentral, which will contain a comprehensive collection of RNA sequences and fill an important gap in the provision of biomedical databases. We envision RNA researchers from all over the world joining a federated RNAcentral network, contributing specialized knowledge and databases. RNAcentral would centralize key data that are currently held across a variety of databases, allowing researchers instant access to a single, unified resource. This resource would facilitate the next generation of RNA research and help drive further discoveries, including those that improve food production and human and animal health. We encourage additional RNA database resources and research groups to join this effort. We aim to obtain international network funding to further this endeavor.
|
|
| 12. |
|
|
| 13. |
|
|
| 14. |
- 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 δ.
|
|
| 15. |
- 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.
|
|
| 16. |
- Fontana, Robert J., et al.
(författare)
-
Daclatasvir combined with sofosbuvir or simeprevir in liver transplant recipients with severe recurrent hepatitis C infection
- 2016
-
Ingår i: Liver transplantation. - : Ovid Technologies (Wolters Kluwer Health). - 1527-6465 .- 1527-6473. ; 22:4, s. 446-458
-
Tidskriftsartikel (refereegranskat)abstract
- Daclatasvir (DCV) is a potent, pangenotypic nonstructural protein 5A inhibitor with demonstrated antiviral efficacy when combined with sofosbuvir (SOF) or simeprevir (SMV) with or without ribavirin (RBV) in patients with chronic hepatitis C virus (HCV) infection. Herein, we report efficacy and safety data for DCV-based all-oral antiviral therapy in liver transplantation (LT) recipients with severe recurrent HCV. DCV at 60mg/day was administered for up to 24 weeks as part of a compassionate use protocol. The study included 97 LT recipients with a mean age of 59.3 +/- 8.2 years; 93% had genotype 1 HCV and 31% had biopsy-proven cirrhosis between the time of LT and the initiation of DCV. The mean Model for End-Stage Liver Disease (MELD) score was 13.0 +/- 6.0, and the proportion with Child-Turcotte-Pugh (CTP) A/B/C was 51%/31%/12%, respectively. Mean HCV RNA at DCV initiation was 14.3x6 log(10) IU/mL, and 37% had severe cholestatic HCV infection. Antiviral regimens were selected by the local investigator and included DCV+SOF (n=77), DCV+SMV (n=18), and DCV+SMV+SOF (n=2); 35% overall received RBV. At the end of treatment (EOT) and 12 weeks after EOT, 88 (91%) and 84 (87%) patients, respectively, were HCV RNA negative or had levels <43 IU/mL. CTP and MELD scores significantly improved between DCV-based treatment initiation and last contact. Three virological breakthroughs and 2 relapses occurred in patients treated with DCV+SMV with or without RBV. None of the 8 patient deaths (6 during and 2 after therapy) were attributed to therapy. In conclusion, DCV-based all-oral antiviral therapy was well tolerated and resulted in a high sustained virological response in LT recipients with severe recurrent HCV infection. Most treated patients experienced stabilization or improvement in their clinical status.
|
|
| 17. |
- Fritzsch, Guido, et al.
(författare)
-
PCR Survey of Xenoturbella bocki Hox Genes
- 2008
-
Ingår i: JOURNAL OF EXPERIMENTAL ZOOLOGY (MOL DEV EVOL). - : Wiley. ; 310B:3, s. 278-284
-
Tidskriftsartikel (refereegranskat)abstract
- Xenoturbella bocki has recently been identified as one of the most basal deuterostomes, although an even more basal phylogenetic position cannot be ruled out. Here we report on a polymerase chain reaction survey of partial Hox homeobox sequences of X. bocki. Surprisingly, we did not find evidence for more than five Hox genes, one clear labial/PG1 ortholog, one posterior gene most similar to the PG9/10 genes of Ambulacraria, and three central group genes whose precise assignment to a specific paralog group remains open. We furthermore report on a re-evaluation of the available published evidence of Hox genes in other basal deuterostomes.
|
|
| 18. |
- Hamdi, Yosr, et al.
(författare)
-
Association of breast cancer risk in BRCA1 and BRCA2 mutation carriers with genetic variants showing differential allelic expression : identification of a modifier of breast cancer risk at locus 11q22.3
- 2017
-
Ingår i: Breast Cancer Research and Treatment. - : Springer Science and Business Media LLC. - 0167-6806 .- 1573-7217. ; 161:1, s. 117-134
-
Tidskriftsartikel (refereegranskat)abstract
- Purpose: Cis-acting regulatory SNPs resulting in differential allelic expression (DAE) may, in part, explain the underlying phenotypic variation associated with many complex diseases. To investigate whether common variants associated with DAE were involved in breast cancer susceptibility among BRCA1 and BRCA2 mutation carriers, a list of 175 genes was developed based of their involvement in cancer-related pathways. Methods: Using data from a genome-wide map of SNPs associated with allelic expression, we assessed the association of ~320 SNPs located in the vicinity of these genes with breast and ovarian cancer risks in 15,252 BRCA1 and 8211 BRCA2 mutation carriers ascertained from 54 studies participating in the Consortium of Investigators of Modifiers of BRCA1/2. Results: We identified a region on 11q22.3 that is significantly associated with breast cancer risk in BRCA1 mutation carriers (most significant SNP rs228595 p = 7 × 10−6). This association was absent in BRCA2 carriers (p = 0.57). The 11q22.3 region notably encompasses genes such as ACAT1, NPAT, and ATM. Expression quantitative trait loci associations were observed in both normal breast and tumors across this region, namely for ACAT1, ATM, and other genes. In silico analysis revealed some overlap between top risk-associated SNPs and relevant biological features in mammary cell data, which suggests potential functional significance. Conclusion: We identified 11q22.3 as a new modifier locus in BRCA1 carriers. Replication in larger studies using estrogen receptor (ER)-negative or triple-negative (i.e., ER-, progesterone receptor-, and HER2-negative) cases could therefore be helpful to confirm the association of this locus with breast cancer risk.
|
|
| 19. |
- 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.
|
|
| 20. |
- 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.
|
|
| 21. |
- 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.
|
|
| 22. |
- 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)
|
|
| 23. |
- 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.
|
|
| 24. |
- Hjelm, Barbara, et al.
(författare)
-
Generation of monospecific antibodies based on affinity capture of polyclonal antibodies
- 2011
-
Ingår i: Protein Science. - : Wiley. - 0961-8368 .- 1469-896X. ; 20:11, s. 1824-1835
-
Tidskriftsartikel (refereegranskat)abstract
- A method is described to generate and validate antibodies based on mapping the linear epitopes of a polyclonal antibody followed by sequential epitope-specific capture using synthetic peptides. Polyclonal antibodies directed towards four proteins RBM3, SATB2, ANLN, and CNDP1, potentially involved in human cancers, were selected and antibodies to several non-overlapping epitopes were generated and subsequently validated by Western blot, immunohistochemistry, and immunofluorescence. For all four proteins, a dramatic difference in functionality could be observed for these monospecific antibodies directed to the different epitopes. In each case, at least one antibody was obtained with full functionality across all applications, while other epitope-specific fractions showed no or little functionality. These results present a path forward to use the mapped binding sites of polyclonal antibodies to generate epitope-specific antibodies, providing an attractive approach for large-scale efforts to characterize the human proteome by antibodies.
|
|
| 25. |
- 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.
|
|
| 26. |
- 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.
|
|
| 27. |
- Kutsche, Lisa K., et al.
(författare)
-
Combined Experimental and System-Level Analyses Reveal the Complex Regulatory Network of miR-124 during Human Neurogenesis
- 2018
-
Ingår i: Cell systems. - : Elsevier BV. - 2405-4712. ; 7:4, s. 438-452
-
Tidskriftsartikel (refereegranskat)abstract
- Non-coding RNAs regulate many biological processes including neurogenesis. The brain-enriched miR-124 has been assigned as a key player of neuronal differentiation via its complex but little understood regulation of thousands of annotated targets. To systematically chart its regulatory functions, we used CRISPR/Cas9 gene editing to disrupt all six miR-124 alleles in human induced pluripotent stem cells. Upon neuronal induction, miR-124-deleted cells underwent neurogenesis and became functional neurons, albeit with altered morphology and neurotransmitter specification. Using RNA-induced-silencing-complex precipitation, we identified 98 high-confidence miR-124 targets, of which some directly led to decreased viability. By performing advanced transcription-factor-network analysis, we identified indirect miR-124 effects on apoptosis, neuronal subtype differentiation, and the regulation of previously uncharacterized zinc finger transcription factors. Our data emphasize the need for combined experimental- and system-level analyses to comprehensively disentangle and reveal miRNA functions, including their involvement in the neurogenesis of diverse neuronal cell types found in the human brain.
|
|
| 28. |
- Le Duc, Diana, et al.
(författare)
-
Kiwi genome provides insights into evolution of a nocturnal lifestyle
- 2015
-
Ingår i: Genome Biology. - : Springer Science and Business Media LLC. - 1465-6906 .- 1474-760X. ; 16
-
Tidskriftsartikel (refereegranskat)abstract
- Background: Kiwi, comprising five species from the genus Apteryx, are endangered, ground-dwelling bird species endemic to New Zealand. They are the smallest and only nocturnal representatives of the ratites. The timing of kiwi adaptation to a nocturnal niche and the genomic innovations, which shaped sensory systems and morphology to allow this adaptation, are not yet fully understood. Results: We sequenced and assembled the brown kiwi genome to 150-fold coverage and annotated the genome using kiwi transcript data and non-redundant protein information from multiple bird species. We identified evolutionary sequence changes that underlie adaptation to nocturnality and estimated the onset time of these adaptations. Several opsin genes involved in color vision are inactivated in the kiwi. We date this inactivation to the Oligocene epoch, likely after the arrival of the ancestor of modern kiwi in New Zealand. Genome comparisons between kiwi and representatives of ratites, Galloanserae, and Neoaves, including nocturnal and song birds, show diversification of kiwi's odorant receptors repertoire, which may reflect an increased reliance on olfaction rather than sight during foraging. Further, there is an enrichment of genes influencing mitochondrial function and energy expenditure among genes that are rapidly evolving specifically on the kiwi branch, which may also be linked to its nocturnal lifestyle. Conclusions: The genomic changes in kiwi vision and olfaction are consistent with changes that are hypothesized to occur during adaptation to nocturnal lifestyle in mammals. The kiwi genome provides a valuable genomic resource for future genome-wide comparative analyses to other extinct and extant diurnal ratites.
|
|
| 29. |
|
|
| 30. |
|
|
| 31. |
|
|
| 32. |
- Mahdessian, Diana, 1984-, et al.
(författare)
-
An image-based map of the human mitochondrial proteome and its heterogeneity
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Mitochondria is involved in a numerous variety of cellular functions beyond its role in energy metabolism. Defining the human mitochondrial proteome is crucial to understand the mitochondria’s diverse functions and role in disease. Here, we present an image-based map of the human mitochondrial proteome containing 1,098 proteins. The single cell resolution revealed extensive heterogeneity for as much as 20% (n=226) of the mitochondrial proteome. These variations are independent of cell cycle position and likely represent metabolic fluctuations in the cell. Our analysis shows that 48% (n=524) of the proteins localize to additional cellular compartments, further contributing to the diverse cellular functions of mitochondria. This map of the mitochondrial proteome, part of the Cell Atlas of the Human Protein Atlas database (www.proteinatlas.org), provides a valuable knowledge resource for studies of mitochondria function, dysfunction and disease.
|
|
| 33. |
- Mahdessian, Diana, et al.
(författare)
-
Profiling the human cytoplasmic proteome.
- 2016
-
Ingår i: Molecular Biology of the Cell. - : AMER SOC CELL BIOLOGY. - 1059-1524 .- 1939-4586. ; 27
-
Tidskriftsartikel (refereegranskat)
|
|
| 34. |
- 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.
|
|
| 35. |
- Marz, Manja, et al.
(författare)
-
Animal snoRNAs and scaRNAs with exceptional structures
- 2011
-
Ingår i: RNA Biology. - : Informa UK Limited. - 1547-6286 .- 1555-8584. ; 8:6, s. 938-946
-
Tidskriftsartikel (refereegranskat)abstract
- The overwhelming majority of small nucleolar RNAs (snoRNAs) fall into two clearly defined classes characterized by distinctive secondary structures and sequence motifs. A small group of diverse ncRNAs, however, shares the hallmarks of one or both classes of snoRNAs but differs substantially from the norm in some respects. Here, we compile the available information on these exceptional cases, conduct a thorough homology search throughout the available metazoan genomes, provide improved and expanded alignments, and investigate the evolutionary histories of these ncRNA families as well as their mutual relationships.
|
|
| 36. |
- 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.
|
|
| 37. |
- 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.
|
|
| 38. |
- 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.
|
|
| 39. |
- Perseke, Marleen, et al.
(författare)
-
The mitochondrial DNA of Xenoturbella bocki : genomic architecture and phylogenetic analysis
- 2007
-
Ingår i: Theory in biosciences. - : Springer Science and Business Media LLC. - 1431-7613 .- 1611-7530. ; 126:1, s. 35-42
-
Tidskriftsartikel (refereegranskat)abstract
- The phylogenetic position of Xenoturbella bocki has been a matter of controversy since its description in 1949. We sequenced a second complete mitochondrial genome of this species and performed phylogenetic analyses based on the amino acid sequences of all 13 mitochondrial protein-coding genes and on its gene order. Our results confirm the deuterostome relationship of Xenoturbella. However, in contrast to a recently published study (Bourlat et al. in Nature 444: 85-88, 2006), our data analysis suggests a more basal branching of Xenoturbella within the deuterostomes, rather than a sister-group relationship to the Ambulacraria (Hemichordata and Echinodermata).
|
|
| 40. |
- Rohrschneider, Markus, et al.
(författare)
-
Visual Network Analysis of Dynamic Metabolic Pathways
- 2010
-
Ingår i: Advances in Visual Computing. - Berlin Heidelberg New Work : Springer. - 3642172881 ; , s. 316-327
-
Konferensbidrag (refereegranskat)abstract
- We extend our previous work on the exploration of static metabolic networks to evolving, and therefore dynamic, pathways. We apply our visualization software to data from a simulation of early metabolism. Thereby, we show that our technique allows us to test and argue for or against different scenarios for the evolution of metabolic pathways. This supports a profound and efficient analysis of the structure and properties of the generated metabolic networks and its underlying components, while giving the user a vivid impression of the dynamics of the system. The analysis process is inspired by Ben Shneiderman’s mantra of information visualization. For the overview, user-defined diagrams give insight into topological changes of the graph as well as changes in the attribute set associated with the participating enzymes, substances and reactions. This way, “interesting features” in time as well as in space can be recognized. A linked view implementation enables the navigation into more detailed layers of perspective for in-depth analysis of individual network configurations.
|
|
| 41. |
- 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.
|
|
| 42. |
- 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.
|
|
| 43. |
- 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.
|
|
| 44. |
- 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.
|
|
| 45. |
- 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.
|
|
| 46. |
- 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.
|
|
| 47. |
- 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.
|
|
| 48. |
- 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.
|
|
| 49. |
- 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.
|
|
| 50. |
- 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.
|
|
