Search
Filters
total: 401
filtered: 365
Search results for: phylogenetic tree metrics
-
Analyzing sets of phylogenetic trees using metrics
PublicationThe reconstruction of evolutionary trees is one of the primary objectives in phylogenetics. Such a tree represents historical evolutionary relationships between different species or organisms. Tree comparisons are used for multiple purposes, from unveiling the history of species to deciphering evolutionary associations among organisms and geographical areas. In this paper, we describe a general method for comparing phylogenetictrees...
-
Generalization of Phylogenetic Matching Metrics with Experimental Tests of Practical Advantages
PublicationThe ability to quantify a dissimilarity of different phylogenetic trees is required in various types of phylogenetic studies, for example, such metrics are used to assess the quality of phylogeny construction methods and to define optimization criteria in supertree building algorithms. In this article, starting from the already described concept of matching metrics, we define three new metrics for rooted phylogenetic trees. One...
-
Critical Case Stochastic Phylogenetic Tree Model via the Laplace Transform
PublicationBirth–and–death models are now a common mathematical tool to describe branching patterns observed in real–world phylogenetic trees. Liggett and Schinazi (2009) is one such example. The authors propose a simple birth–and–death model that is compatible with phylogenetic trees of both influenza and HIV, depending on the birth rate parameter. An interesting special case of this model is the critical case where the birth rate equals the...
-
Analyzing sets of phylogenetic trees obtained from bayesian MCMC process using topology metrics
PublicationThe reconstruction of evolutionary trees is one of the primary objectives in phylogenetics. Such a tree represents historical evolutionary relationship between different species or organisms. Tree comparisons are used for multiple purposes, from unveiling the history of species to deciphering evolutionary associations amongorganisms and geographical areas.In the paper, we describe a general method for comparing hylogenetic trees....
-
Comparing phylogenetic trees using a minimum weight perfect matching
PublicationA phylogenetic tree represents historical evolutionary relationshipbetween different species or organisms. There are various methods for reconstructing phylogenetic trees.Applying those techniques usually results in different treesfor the same input data. An important problem is to determinehow distant two trees reconstructed in such a wayare from each other. Comparing phylogenetic trees is alsouseful in mining phylogenetic information...
-
Visual TreeCmp : Comprehensive Comparison of Phylogenetic Trees on the Web
Publication1. We present Visual TreeCmp—a package of applications for comparing phylogenetic tree sets. 2. Visual TreeCmp includes a graphical web interface allowing the visualization of compared trees and command line application extended by comparison methods recently proposed in the literature. 3. The phylogenetic tree similarity analysis in Visual TreeCmp can be performed using eighteen metrics, of which 11 are dedicated to rooted trees...
-
Comparing Arbitrary Unrooted Phylogenetic Trees Using Generalized Matching Split Distance
PublicationIn the paper, we describe a method for comparing arbitrary, not necessary fully resolved, unrooted phylogenetic trees. Proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of presented distance in a common biological problem...
-
Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions
PublicationAbility to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in...
-
Psychological and physical components in forming preferences on urban greenery management – The case of trees
PublicationPublic opinion is increasingly important in managing urban greenery. In this regard, this study demonstrates the importance of sociological (environmental worldviews), psychological (place attachment, perceived benefits of trees), and physical factors (type of building people live in, and urban greenery) in forming residents’ opinions on whether the municipality or landowners should decide about tree removal on private land. Logistic...
-
Intra-operative biopsy in chronic sinusitis detects pathogenic Escherichia coli that carry fimG/H, fyuA and agn43 genes coding biofilm formation
PublicationThe aim of this study was to investigate whether or not surgical biopsy of sinus tissue in chronic sinusitis, not responsive to treatment, would detect E. coli. We intended to evaluate E. coli virulence genes, therefore dispute the causal role of such an unusual microorganism in chronic sinusitis, as well as consider effective pathogen-targeted therapy. Patients with E. coli isolated by intra-operative puncture biopsy were included...
-
Metrics for green analytical chemistry
PublicationGreen analytical chemistry, although not being a new concept, does not have a greenness metrics system. Green chemistry metrics are not suitable for analytical procedure assessment because they often refer to the mass of the product. Some efforts have been made to develop suitable metrics for analytical chemistry. Some are simple to use but do not cover all aspects of analytical methods’ environmental impact. Others are more comprehensive...
-
Green analytical chemistry metrics: A review
PublicationGreen analytical chemistry encourages reducing the use of toxic chemicals/reagents, using energy-efficient equipment, and generating minimal waste. The recent trends in analytical method development focus on the miniaturization of the sample preparation devices, the development of solventless or solvent-minimized extraction techniques, and the utilization of less toxic solvents. The twelve principles of GAC serve as a basic guideline...
-
Construction of phylogenetic trees with topological constraints
PublicationThis paper proposes a method of reconstruction of phylogenetic trees based on heuristic search with topological constraints. Using topological constraints it is possible to reduce the set of solutions as well as to enforce that the result is consistent with a given hypothesis about the evolution process within some group of species. Along with this work a number of algorithms used for phylogenetic analysis were implemented. Those...
-
The complexity of bicriteria tree-depth
PublicationThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
Data-driven Models for Predicting Compressive Strength of 3D-printed Fiber-Reinforced Concrete using Interpretable Machine Learning Algorithms
Publication3D printing technology is growing swiftly in the construction sector due to its numerous benefits, such as intricate designs, quicker construction, waste reduction, environmental friendliness, cost savings, and enhanced safety. Nevertheless, optimizing the concrete mix for 3D printing is a challenging task due to the numerous factors involved, requiring extensive experimentation. Therefore, this study used three machine learning...
-
Polynomial triset metric for unrooted phylogenetic trees
Publicationthe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
Aiming at methods’ wider adoption: Applicability determinants and metrics
PublicationNumerous computer science methods and techniques have been proposed by the scientific community. However, depending on the domain, only their minor fraction has met wider adoption. This paper brings attention to the concept of applicability - the notion that is well acknowledged in the scientific field but have not been analysed with respect to determinants, metrics and systematisation. The primary objective of the study was to...
-
Green Chemistry Metrics with Special Reference to Green Analytical Chemistry
PublicationThe concept of green chemistry is widely recognized in chemical laboratories. To properly measure an environmental impact of chemical processes, dedicated assessment tools are required. This paper summarizes the current state of knowledge in the field of development of green chemistry and green analytical chemistry metrics. The diverse methods used for evaluation of the greenness of organic synthesis, such as eco-footprint, E-Factor,...
-
On extremal sizes of locally k-tree graphs
PublicationA graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...
-
The reliability of tree and star networks
PublicationThis paper investigated the reliability of tree and star networks. Following measures of network reliability are assumed: the expected number of nodes, that can communicate with the central node; the expected number of node pairs, that are connected by a path through the central node; the expected number of node pairs communicating.
-
Evaluation of the content of inorganic anions in tree saps
PublicationTree saps were once commonly used in the countries of Northern, Central and Eastern Europe. Although once almost forgotten, their popularity has been growing recently as part of an interest in organic food and traditional medicine. Tree saps, tapped mainly from birch and maple trees, are drunk both fresh and fermented or are used as raw material for the production of food products, e.g. syrups. The aim of this study was to determine...
-
On a matching distance between rooted phylogenetic trees
PublicationThe Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...
-
Incremental construction of Minimal Tree Automata [online]
PublicationWe describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...
-
EXPERIMENTAL ANALYSIS OF CONNECTION BETWEEN OBJECT-ORIENTED METRICS AND SOFTWARE CHANGEABILITY
PublicationFor the purpose of video surveillance software quality assessment in this work the ISO/IEC-9126 norm was used with a particular focus on maintainability of the software system. The paper presents a study on the connection between software metrics derived from the static analysis of the source code and changeability of the video surveillance software system. It is shown that meeting requirements of software quality metrics may result...
-
Web Services Integration with Regard to the Metrics of Data Believability
PublicationThe paper is concerned with estimating the believability of data acquired from web services. In the paper, a new method for believability estimation is introduced. The method is designed for integrating web services. The believability estimation is based on the following metrics: quantity, reputation, approval, independence, traceability, maturity, authority and objectivity. In the method, data trustworthiness is determined by...
-
The reliability of tree and star networks.
PublicationOne of the important parameters characterizing the quality of computer networks is the network's reliability with respect to failures of the communication links and nodes. This chapter investigated the reliability of tree and star networks. The tree and star topology is used in centralized computer networks. In centralized computer networks all communication must take place through some central computer. Following measures of network...
-
Average Size of a Suffix Tree for Markov Sources
PublicationWe study a suffix tree built from a sequence generated by a Markovian source. Such sources are more realistic probabilistic models for text generation, data compression, molecular applications, and so forth. We prove that the average size of such a suffix tree is asymptotically equivalent to the average size of a trie built over n independentsequences from the same Markovian source. This equivalenceis only known for memoryless...
-
Perfect hashing tree automata
PublicationWe present an algorithm that computes a function that assigns consecutive integers to trees recognized by a deterministic, acyclic, finite-state, bottom-up tree automaton. Such function is called minimal perfect hashing. It can be used to identify trees recognized by the automaton. Its value may be seen as an index in some other data structures. We also present an algorithm for inverted hashing.Przedstawiamy algorytm, który oblicza...
-
An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree
PublicationWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.
-
An algorithm for listing all minimal double dominating sets of a tree
PublicationWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Situational Awareness Network for the Electric Power System: the Architecture and Testing Metrics
PublicationThe contemporary electric power system is highly dependent on Information and Communication Technologies which results in its exposure to new types of threats, such as Advanced Persistent Threats (APT) or Distributed-Denial-of-Service (DDoS) attacks. The most exposed components are Industrial Control Systems in substations and Distributed Control Systems in power plants. Therefore, it is necessary to ensure the cyber security of...
-
MINERAL CONTENT OF TREE SAP FROM THE SUBCARPATHIAN REGION
Publicationbut also as medicinal substance in folk medicine. Traditionally, it was used to treat various conditions, mostly anaemia and chronic fatigue. This study has been designed to establish the content of metallic elements (sodium, potassium, calcium, magnesium, zinc and copper) in sap collected from eight different species (silver birch, downy birch, hornbeam, Norway maple, boxelder maple, black walnut, black alder and white willow)...
-
Selecting an Applicable Cybersecurity Assessment Framework: Qualitative Metrics-Based Multiple-Factor Analysis
PublicationRecently, a survey of cybersecurity assessment methods focused on general characteristics was conducted. Among its major findings, it revealed the methods’ adoption issues. This paper presents a follow-up to the study. It provides an in-depth analysis of the methods’ adoption-related properties based on qualitative metrics. As a result, the proposals which demonstrate a higher adoption potential were identified. The methods are...
-
Bounds on the vertex-edge domination number of a tree
PublicationA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Empirical analysis of tree-based classification models for customer churn prediction
PublicationCustomer churn is a vital and reoccurring problem facing most business industries, particularly the telecommunications industry. Considering the fierce competition among telecommunications firms and the high expenses of attracting and gaining new subscribers, keeping existing loyal subscribers becomes crucial. Early prediction of disgruntled subscribers can assist telecommunications firms in identifying the reasons for churn and...
-
Atmospheric deposition in coniferous and deciduous tree stands in Poland
PublicationThe objective of this study was to assess the transformation of precipitation in terms of quantity and chemical composition following contact with the crown layer in tree stands with varied species composition, to investigate the effect of four predominant forest-forming species (pine, spruce, beech, and oak) on the amount and composition of precipitation reaching forest soils, and to determine the sources of pollution in atmospheric...
-
High prevalence of Escherichia coli belonging to the B2+D phylogenetic group in inflammatory bowel disease
PublicationBACKGROUND: It is not clear which species of bacteria may be involved in inflammatory bowel disease (IBD). One way of determining which bacteria might be likely candidates is to use culture-independent methods to identify microorganisms that are present in diseased tissues but not in controls. AIMS: (1) To assess the diversity of microbial communities of biopsy tissue using culture-independent methods; (2) to culture the bacteria...
-
Gossiping by energy-constrained mobile agents in tree networks
PublicationEvery node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently...
-
Perfect hashing with pseudo-minimal bottom-up deterministic tree automata
PublicationWe describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally...
-
A lower bound on the total outer-independent domination number of a tree
PublicationA total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n-2l+2)/3,...
-
The variability of macrophyte metrics used in river monitoring
Publication -
An upper bound on the 2-outer-independent domination number of a tree
PublicationA 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2-outer-independent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2,...
-
An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree
PublicationA 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination...
-
An upper bound on the total outer-independent domination number of a tree
PublicationA total outer-independent dominating set of a graph G=(V(G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n >= 4, with l leaves and s support vertices we have...
-
Antibiotic resistance, virulence, and phylogenetic analysis of Escherichia coli strains isolated from free-living birds in human habitats
PublicationWild birds can be colonized by bacteria, which are often resistant to antibiotics and have various virulence profiles. The aim of this study was to analyze antibiotic resistance mechanisms and virulence profiles in relation to the phylogenetic group of E. coli strains that were isolated from the GI tract of wildfowl. Out of 241 faecal samples, presence of E. coli resistant to a cephalosporin (ESBL/AmpC) was estimated for 33 isolates...
-
Properties of the triset metric for phylogenetic trees
Publicationthe following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.
-
An upper bound for the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)\D is independent. The double outer-independent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
A lower bound on the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
Use of Bi-Temporal ALS Point Clouds for Tree Removal Detection on Private Property in Racibórz, Poland
PublicationTrees growing on private property have become an essential part of urban green policies. In many places, restrictions are imposed on tree removal on private property. However, monitoring compliance of these regulations appears difficult due to a lack of reference data and public administration capacity. We assessed the impact of the temporary suspension of mandatory permits on tree removal, which was in force in 2017 in Poland,...
-
The energy consumption during the birch tree sap concentration process using the reverse osmosis system
PublicationBirch tree sap was concentrated by mens of the reversed osmosis technique. The energy consumption in a small-scale pilot apparatus was estimated. The threshold value for the water removal above which the specific energy consumption significantly increased was identified. Below the threshold value the reversed osmosis had low energy demand and could be an attractive method for the production of birch tree sap-based beverages.