首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.

Background

In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer.

Results

We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an \(\mathcal {O}(|V(T)|\log (|V(S)|))\)-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. The algorithms are implemented in C++ using the boost graph library and are freely available at https://github.com/Nojgaard/tc-recon.

Significance

The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems.
  相似文献   

2.
In this study we are concerned with the general problem of choosing from a set of endangered species T a subset S of k species to protect as a priority. Here, the interest to protect the species of S is assessed by the resulting expected phylogenetic diversity (ePD) of the set T, a widely used criterion for measuring the expected amount of evolutionary history associated with T. We consider that the survival of the protected species is assured and, on the contrary, that there is a risk of extinction for the unprotected species. The problem is easy to solve by a greedy type method if the extinction probabilities of the unprotected species are known but these probabilities are generally not easy to quantify. We show in this note that the choice of the precise values attributed to the extinction probabilities—provided it respects the rank of imperilment of each species—is not as decisive as might be feared for the considered problem. The values of these probabilities have a clear impact on the selection of the species to be protected but a little impact on the resulting ePD. More precisely, if T 1 and T 2 are the two optimal subsets of species corresponding to two scenarios (two different sets of probabilities) the ePDs of T 1 and T 2, calculated with the probabilities of the first scenario—or with the probabilities of the second scenario—are not very different.  相似文献   

3.

Background

Isometric gene tree reconciliation is a gene tree/species tree reconciliation problem where both the gene tree and the species tree include branch lengths, and these branch lengths must be respected by the reconciliation. The problem was introduced by Ma et al. in 2008 in the context of reconstructing evolutionary histories of genomes in the infinite sites model.

Results

In this paper, we show that the original algorithm by Ma et al. is incorrect, and we propose a modified algorithm that addresses the problems that we discovered. We have also improved the running time from \(O(N^2)\) to \(O(N\log N)\), where N is the total number of nodes in the two input trees. Finally, we examine two new variants of the problem: reconciliation of two unrooted trees and scaling of branch lengths of the gene tree during reconciliation of two rooted trees.

Conclusions

We provide several new algorithms for isometric reconciliation of trees. Some questions in this area remain open; most importantly extensions of the problem allowing for imprecise estimates of branch lengths.
  相似文献   

4.
In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree—a tree having its leaves labeled bijectively by elements of X and without degree-2 nodes—called the “species tree.” One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the “concordance” with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping—but not identical—sets of labels, is called “supertree.” In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of “containing as a minor” and “containing as a topological minor” in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees k, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time \(2^{O(k^2)} \cdot n\), where n is the total size of the input.  相似文献   

5.
Two new approaches to detecting potential incongruence between a protein family tree and a species tree are considered. The first approach is based on the substitution of a known mapping of the gene tree G into the species tree S with a somewhat analogous multivalued G-into-S mapping. The second approach is based on the elementary concepts of the fuzzy set theory. Two algorithms corresponding to these approaches are described in detail, and their implementation is shown using a simulation example and three protein families from the database of clusters of orthologous protein groups (COGs).  相似文献   

6.
We consider a set of species S and are interested in the assessment of the subsets of S from a phylogenetic diversity viewpoint. Several measures can be used for this assessment. Here we have retained phylogenetic diversity (PD) in the sense of Faith, a measure widely used to reflect the evolutionary history accumulated by a group of species. The PD of a group of species X included in S is easy to calculate when the phylogenetic tree associated with S is perfectly known but this situation is rarely verified. We are interested here in cases where uncertainty regarding the length of branches and the topology of the tree is reflected in the fact that several phylogenetic trees are considered to be plausible for the set S. We propose several measures of the phylogenetic diversity to take account of the uncertainty arising from this situation. A natural problem in the field of biological conservation is to select the best subset of species to protect from a group of threatened species. Here, the best subset is the one that optimizes the proposed measures. We show how to solve these optimal selection problems by integer linear programming. The approach is illustrated by several examples.  相似文献   

7.
We assembled a dataset tabulating the weights of Thai and Indonesian mangrove trees that we measured between 1982 and 2001. We selected four Thai study sites in Phang Nga, Ranong, Satun, and Trat Provinces and one site in eastern Indonesia on Halmahera Island in Maluku Province. The stands in Ranong Province and on Halmahera Island were in primary forests with data collected in the 1980s and the remaining stands were in secondary forests with data collected later. We collected 124 tree samples from ten species (Avicennia alba, Bruguiera cylindrica, B. gymnorrhiza, Ceriops tagal, Rhizophora apiculata, R. mucronata, Sonneratia alba, S. caseolaris, Xylocarpus granatum, and X. moluccensis) and measured the root weights of 32 individuals of nine species (A. alba, B. cylindrica, B. gymnorrhiza, C. tagal, R. apiculata, R. mucronata, S. alba, S. caseolaris, and X. granatum). All sampled trees were subjected to a standardized protocol to obtain aboveground weights. The trunks were divided into horizontal segments from which the leaves and branches were collected separately. Roots were collected by winching them out of the ground, by trench digging, or by complete excavation. Thus, we were able to compile the weights of the trunk, branches, leaves, and roots of each tree sampled. Aerial roots were included in root weight measurements, although they were collected above ground. We compiled separate lists of trunk diameters, trunk heights, heights of the lowest living branches, and the heights of aerial roots on the trunks of trees in different size categories. Our dataset includes a wide range of tree sizes (maximum trunk diameter 48.9 cm), geographical locations (1°10′N–12°24′N, 98°32′E–123°49′E) and organ weights (trunks, branches, leaves, and roots), and therefore should prove useful in future biomass studies of mangrove forests.  相似文献   

8.
The larch bark beetle (Ips subelongatus), which occurs in larch plantations over a vast area of eastern Asia, infects both dying and fallen trees. When its population reaches a high density, the beetle may also infect healthy trees, resulting in tree decline and, eventually, death. Leptographium spp., in both their sexual and asexual states, are mainly associated with conifer-infesting bark beetles; some species are important tree pathogens. The aims of this study were to identify the Leptographium spp. associated with I. subelongatus infestations of Larix spp. in northern China and to examine their pathogenicity towards the tree. Morphological studies and phylogenetic approaches based on multilocus DNA sequence data (ITS2- partial r28S, partial β-tubulin, and EF-1α gene regions) showed that three Leptographium species occur in association with I. subelongatus in the areas investigated: Leptographium taigense, which is recorded in China for the first time, and two new species, namely L. innermongolicum sp. nov. and L. zhangii sp. nov. Leptographium innermongolicum is closely related to L. taigense, whereas L. zhangii belongs to the Grosmannia piceaperda species complex. The pathogenicity of these Leptographium species towards mature Larix spp. was tested by stem inoculation in forests. All inoculations only resulted in small lesions on the inner bark; therefore, the three Leptographium species were not considered to be pathogenic.  相似文献   

9.

Background

For a combination of reasons (including data generation protocols, approaches to taxon and gene sampling, and gene birth and loss), estimated gene trees are often incomplete, meaning that they do not contain all of the species of interest. As incomplete gene trees can impact downstream analyses, accurate completion of gene trees is desirable.

Results

We introduce the Optimal Tree Completion problem, a general optimization problem that involves completing an unrooted binary tree (i.e., adding missing leaves) so as to minimize its distance from a reference tree on a superset of the leaves. We present OCTAL, an algorithm that finds an optimal solution to this problem when the distance between trees is defined using the Robinson–Foulds (RF) distance, and we prove that OCTAL runs in \(O(n^2)\) time, where n is the total number of species. We report on a simulation study in which gene trees can differ from the species tree due to incomplete lineage sorting, and estimated gene trees are completed using OCTAL with a reference tree based on a species tree estimated from the multi-locus dataset. OCTAL produces completed gene trees that are closer to the true gene trees than an existing heuristic approach in ASTRAL-II, but the accuracy of a completed gene tree computed by OCTAL depends on how topologically similar the reference tree (typically an estimated species tree) is to the true gene tree.

Conclusions

OCTAL is a useful technique for adding missing taxa to incomplete gene trees and provides good accuracy under a wide range of model conditions. However, results show that OCTAL’s accuracy can be reduced when incomplete lineage sorting is high, as the reference tree can be far from the true gene tree. Hence, this study suggests that OCTAL would benefit from using other types of reference trees instead of species trees when there are large topological distances between true gene trees and species trees.
  相似文献   

10.
An endophytic actinobacterial strain was isolated from a yellowwood tree growing on the slope of Devil’s Peak, Cape Town, South Africa. Analysis of the 16S rRNA gene showed that the strain belongs to the genus Kribbella. Phylogenetic analyses using the 16S rRNA gene and multilocus sequence analysis using the concatenated gene sequences of the gyrB, rpoB, relA, recA and atpD genes showed that strain YPL1T is closely related to the type strains of Kribbella karoonensis and Kribbella shirazensis. DDH experiments showed that strain YPL1T is a distinct genomic species from its close phylogenetic relative, K. karoonensis Q41T. Physiological comparisons further showed that strain YPL1T is phenotypically distinct from the type strains of Kribbella jejuensis, Kribbella aluminosa, K. karoonensis, K. shirazensis and Kribbella swartbergensis. Strain YPL1T is thus presented as the type strain of a novel species, for which the name Kribbella podocarpi sp. nov. (= DSM 29424T = NRRL B-65063T), is proposed.  相似文献   

11.

Background

Selection criteria are important for analyzing domestication of perennial plant species, which experience a selection pressure throughout several human generations. We analyze the preferred morphological characteristics of Crescentia cujete fruits, which are used as bowls by the Maya of Yucatan, according to the uses they are given and the phenotypic consequences of artificial selection between one wild and three domesticated varieties.

Methods

We performed 40 semi-structured interviews in seven communities. We calculated Sutrop’s salience index (S) of five classes of ceremonial and daily life uses, and of each item from the two most salient classes. We sampled 238 bowls at homes of people interviewed and compared their shape, volume and thickness with 139 fruits collected in homegardens and 179 from the wild. Morphology of varieties was assessed in fruit (n?=?114 trees) and vegetative characters (n?=?136 trees). Differences between varieties were evaluated through linear discriminant analysis (LDA).

Results

Use of bowls as containers for the Day of the Dead offerings was the most salient class (S?=?0.489) with chocolate as its most salient beverage (S?=?0.491), followed by consumption of daily beverages (S?=?0.423), especially maize-based pozol (S?=?0.412). The sacred saka’ and balche' are offered in different sized bowls during agricultural and domestic rituals. Roundness was the most relevant character for these uses, as bowls from households showed a strong selection towards round shapes compared with wild and homegarden fruits. Larger fruits from domesticated varieties were also preferred over small wild fruits, although in the household different sizes of the domesticated varieties are useful. LDA separated wild from domesticated trees (p?<?0.001) according to both fruit and vegetative variables, but domesticated varieties were not different among themselves.

Conclusions

The association between C. cujete bowls and traditional beverages in ritual and daily life situations has driven for centuries the selection of preferred fruit morphology in this tree. Selection of fruit roundness and volume has allowed for the differentiation between the wild variety and the three domesticated ones, counteracting gene flow among them. By choosing the best fruits from domesticated varieties propagated in homegardens, the Maya people model the domestication process of this important tree in their culture.
  相似文献   

12.
Macaranga is a tree genus that includes many species of myrmecophytes, which are plants that harbor ant colonies within hollow structures known as domatia. The symbiotic ants (plant–ants) protect their host plants against herbivores; this defense mechanism is called ‘ant defense’. A Bornean phasmid species Orthomeria cuprinus feeds on two myrmecophytic Macaranga species, Macaranga beccariana and Macaranga hypoleuca, which are obligately associated with Crematogaster ant species. The phasmids elude the ant defense using specialized behavior. However, the mechanisms used by the phasmid to overcome ant defenses have been insufficiently elucidated. We hypothesized that O. cuprinus only feeds on individual plants with weakened ant defenses. To test the hypothesis, we compared the ant defense intensity in phasmid-infested and non-infested M. beccariana trees. The number of plant–ants on the plant surface, the ratio of plant–ant biomass to tree biomass, and the aggressiveness of plant–ants towards experimentally introduced herbivores were significantly lower on the phasmid-infested trees than on the non-infested trees. The phasmid nymphs experimentally introduced into non-infested trees, compared with those experimentally introduced into phasmid-infested trees, were more active on the plant surface, avoiding the plant–ants. These results support the hypothesis and suggest that ant defenses on non-infested trees effectively prevent the phasmids from remaining on the plants. Thus, we suggest that O. cuprinus feeds only on the individual M. beccariana trees having decreased ant defenses, although the factors that reduce the intensity of the ant defenses remain unclear.  相似文献   

13.
The taxonomic position of a new Saccharothrix strain, designated MB46T, isolated from a Saharan soil sample collected in Mzab region (Ghardaïa province, South Algeria) was established following a polyphasic approach. The novel microorganism has morphological and chemical characteristics typical of the members of the genus Saccharothrix and formed a phyletic line at the periphery of the Saccharothrix espanaensis subcluster in the 16S rRNA gene dendrograms. Results of the 16S rRNA gene sequence comparisons revealed that strain MB46T shares high degrees of similarity with S. espanaensis DSM 44229T (99.2%), Saccharothrix variisporea DSM 43911T (98.7%) and Saccharothrix texasensis NRRL B-16134T (98.6%). However, the new strain exhibited only 12.5–17.5% DNA relatedness to the neighbouring Saccharothrix spp. On the basis of phenotypic characteristics, 16S rRNA gene sequence comparisons and DNA-DNA hybridizations, strain MB46T is concluded to represent a novel species of the genus Saccharothrix, for which the name Saccharothrix ghardaiensis sp. nov. (type strain MB46T = DSM 46886T = CECT 9046T) is proposed.  相似文献   

14.
A novel actinomycete, designated strain NEAU-mq18T, was isolated from the rhizosphere soil of a rubber tree (Hevea brasiliensis Muell. Arg) collected from Xianglu Mountain in Heilongjiang Province, northeast China, and subjected to a polyphasic taxonomic study. The 16S rRNA gene sequence analysis showed that the isolate belongs to the genus Nonomuraea with high sequence similarity to Nonomuraea guangzhouensis NEAU-ZJ3T (98.5%). Phylogenetic analysis based on 16S rRNA gene sequences indicated that the strain clusters phylogenetically with N. guangzhouensis NEAU-ZJ3T and Nonomuraea glycinis NEAU-BB2C19T. Moreover, key chemotaxonomic properties including the major menaquinones, fatty acid composition and phospholipid profile also confirmed the affiliation of the strain to the genus Nonomuraea. However, some physiological, morphological and biochemical properties, and low DNA–DNA relatedness values, enabled the strain to be differentiated from closely related species of the genus Nonomuraea. Thus, strain NEAU-mq18T is concluded to represent a novel species of the genus Nonomuraea, for which the name Nonomuraea rhizosphaerae sp. nov. is proposed. The type strain is NEAU-mq18T (=CGMCC 4.7431T=DSM 105761T).  相似文献   

15.
Böcker and Dress (Adv Math 138:105–125, 1998) presented a 1-to-1 correspondence between symbolically dated rooted trees and symbolic ultrametrics. We consider the corresponding problem for unrooted trees. More precisely, given a tree T with leaf set X and a proper vertex coloring of its interior vertices, we can map every triple of three different leaves to the color of its median vertex. We characterize all ternary maps that can be obtained in this way in terms of 4- and 5-point conditions, and we show that the corresponding tree and its coloring can be reconstructed from a ternary map that satisfies those conditions. Further, we give an additional condition that characterizes whether the tree is binary, and we describe an algorithm that reconstructs general trees in a bottom-up fashion.  相似文献   

16.
The present study focused on identification and genotypic characterization of Lactic acid bacteria (LAB) in the intestine of freshwater fish. 76 strains of LAB were isolated and identified by 16S rRNA gene sequences and hsp60 gene sequences as different strains of Lactobacillus plantarum, Lactobacillus pentosus, Lactobacillus fermentum, Lactobacillus delbrueckii subsp. bulgaricus, Lactobacillus brevis, Lactobacillus reuteri, Lactobacillus salivarius, Pediococcus pentosaceus, Pediococcus acidilactici, Weissella paramesenteroides, Weissella cibaria, Enterococcus faecium, and Enterococcus durans. The hsp60 gene showed a higher level of sequence variation among the isolates examined, with lower interspecies sequence similarity providing more resolutions at the species level than the 16S rRNA gene. Phylogenetic tree derived from hsp60 gene sequences with higher bootstrap values at the nodal branches was more consistent as compared to phylogenetic tree constructed from 16S rRNA gene sequences. Closely related species L. plantarum and L. pentosus as well as species L. delbrueckii subsp. bulgaricus and L. fermentum were segregated in different cluster in hsp60 phylogenetic tree whereas such a distribution was not apparent in 16S rRNA phylogenetic tree. In silico restriction analysis revealed a high level of polymorphism within hsp60 gene sequences. Restriction pattern with enzymes AgsI and MseI in hsp60 gene sequences allowed differentiation of all the species including closely related species L. plantarum and L. pentosus, E. faecium and E. durans. In general, hsp60 gene with higher evolutionary divergence proved to be a better phylogenetic marker for the group LAB.  相似文献   

17.
Data reflecting evolutionary changes in chromosomal gene order can be used for phylogenetic reconstructions along with the results of nucleotide sequence comparison. By the example of bacteria of the genus Rickettsia, we have shown that phylogenetic reconstructions based on quantitative estimates of the similarity and cladistic analysis of gene order data, may, in some cases, amend and fill up classical phylogenetic trees. When applied, these approaches enabled us to substantiate the hypothesis that Rickettsia felis species had split before the typhus (R. typhi, R. prowazekii) and spotted fever (R. connorii) group divergence and thus R. felis does not belong to the latter group. In general, rickettsias evolved towards increasing intracellular parasitic specialization. Five Rickettsia species whose genomes have been sequenced and annotated completely actually form an evolutionary series R. bellii—R. felis—R. conorii—R. prowazekii—R. typhi. Within this series, a reduction in genome size and rapid decrease of genome rearrangement rates (genome plasticity loss) gradually occur.  相似文献   

18.
The results of analysis of the variability of body shape of different Daphnia galeata morphs from geographically distinct populations—Lake Glubokoe (Moscow oblast) and Lake Chany (Novosibirsk oblast) are given. The morphological analysis was combined with the analysis of the variability of fragments of the 16S and 12S genes of the mitochondrial DNA (mtDNA) and the internal transcribed spacer 2 (ITS2) of the nuclear DNA. A reconstruction of the phylogenetic relationships between species of the genus Daphnia has been performed using a combined fragment of the 16S and 12S genes of the mtDNA. An inconsistency in the distribution of the 12S- and ITS2-haplotypes for the species D. galeata has been revealed, which indicates the introgression of mtDNA in the Lake Chany population.  相似文献   

19.
The taxonomic provenance of a filamentous actinobacterial strain isolated from a desert soil was established using a polyphasic approach. The strain has chemotaxonomic and morphological properties consistent with its classification in the genus Saccharothrix. It forms a distinct branch in the Saccharothrix 16S rRNA gene tree, related to the type strain of Saccharothrix saharensis (96.7%) but was distinguished readily from it using a combination of phenotypic properties. The genotypic and phenotypic data show that the strain represents a novel species in the genus Saccharothrix, for which the name Saccharothrix tharensis sp. nov. is proposed with the type strain TD-093T (=?KCTC 39724T?=?MCC 2832T).  相似文献   

20.
Urban trees form a vital component of sustainable cities but the use of a restricted range of species and genotypes may pose a risk to global biodiversity. Despite several studies investigating tree species diversity, intraspecific genetic diversity of urban trees remains largely unexplored. Here, we characterized the genetic diversity of Tilia?×?europaea, one of the most widely planted urban tree species in Northwest Europe. We compared the genotypic diversity of historical plantings of Tilia spp. from the 17th century with the genotypic diversity of currently available planting stock in Belgium and the Netherlands. In total, 129 trees were sampled and genotyped with 14 microsatellite loci and 150 polymorphic Amplified Fragment Length Polymorphism markers. In Northwest Europe, homogenization of urban T.?×?europaea plantings already started at the 17th century. Genetic diversity within contemporary commercial planting stocks was extremely narrow and consisted mainly of two clones, sold under the name ‘Pallida’ and ‘Zwarte linde’. The genetic diversity found within the historical plantings was about four times higher than in the current commercial planting stocks. We recommend that tree nurseries should enlarge the genetic diversity of T.?×?europaea commercial planting stocks. The old clones have shown long-term disease resistance and could provide tree breeders with the valuable new genetic material. The range of available Tilia species and genotypes needs to be explored in future urban tree planning to optimize desired ecosystem services.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号