A5069094985- Genomics and Phylogenetic Studies
- Genetic diversity and population structure
- Genome Rearrangement Algorithms
- Evolution and Paleontology Studies
- Plant Diversity and Evolution
- Algorithms and Data Compression
- Bioinformatics and Genomic Networks
- Plant and animal studies
- Data Mining Algorithms and Applications
- Chromosomal and Genetic Variations
- Gene expression and cancer classification
- Mycorrhizal Fungi and Plant Interactions
- Advanced Graph Theory Research
- Complexity and Algorithms in Graphs
- Genetic Associations and Epidemiology
- Constraint Satisfaction and Optimization
- Species Distribution and Climate Change
- Plant and Fungal Species Descriptions
- Graph theory and applications
- semigroups and automata theory
- Complex Network Analysis Techniques
- DNA and Biological Computing
- Formal Methods in Verification
- graph theory and CDMA systems
- Plant Taxonomy and Phylogenetics
Delft University of Technology
2016-2025
Institute of Applied Mathematics
2015-2025
Dalhousie University
2019
Centrum Wiskunde & Informatica
2010-2015
Maastricht University
2014
Vrije Universiteit Amsterdam
2014
University of Canterbury
2008-2011
Christ University
2011
Eindhoven University of Technology
2005-2009
The human genome is diploid, which requires assigning heterozygous single nucleotide polymorphisms (SNPs) to the two copies of genome. resulting haplotypes, lists SNPs belonging each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, oblivious direct read information, constitute state-of-the-art. Haplotype assembly, addresses phasing directly from sequencing reads, suffers fact that reads current generation too short serve purposes...
Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships taxa), it is possible to determine in polynomial time whether there exists level-1 network consistent with T, if so, construct such network. Here, we extend this work by showing that problem even solvable for construction level-2 networks. This shows assuming density, tractable plausible histories from when are heavily nontree-like. further strengthens case...
Rooted phylogenetic networks are used to describe evolutionary histories that contain non-treelike events such as hybridization and horizontal gene transfer. In some cases, can be described by a base-tree with additional linking arcs, which can, for example, represent transfer events. Such called tree-based. Here, we consider two possible generalizations of this concept nonbinary networks, call tree-based strictly-tree-based networks. We give simple graph-theoretic characterizations...
With the increasing availability of genomic data, biologists aim to find more accurate descriptions evolutionary histories influenced by secondary contact, where diverging lineages reconnect before again. Such reticulate events can be accurately represented in phylogenetic networks than trees. Since root location not inferred from biological data under several models, we consider semi-directed (phylogenetic) networks: partially directed graphs without a which edges represent events. By...
Abstract Phylogenetic trees are widely used to display estimates of how groups species evolved. Each phylogenetic tree can be seen as a collection clusters, subgroups the that evolved from common ancestor. When obtained for several datasets (e.g. different genes), then their clusters often contradicting. Consequently, set all such dataset cannot combined into single tree. networks generalization more complex evolutionary histories, including reticulate events, hybridizations, recombinations...
A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of simplest possible consistent with input set T, where T contains at least one tree on three leaves (a triplet) for each combination taxa. To quantify complexity both total number and per biconnected component, called level network. We give polynomial-time algorithms...
Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR Subtree Prune Regraft). Recently, these were generalized to networks, which are a more suitable representation reticulate evolutionary histories, it was shown that any two networks same complexity connected by sequence either or moves. Here, we show this is possible using only tail moves, restricted version on closely related trees. The...
Recently, much attention has been devoted to the construction of phylogenetic networks which generalize trees in order accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 networks--a type network slightly more general than a tree--from triplets. Our made publicly available as program LEV1ATHAN. It combines ideas from several known theoretical algorithms tree and reconstruction with two novel subroutines. Namely,...
Binets and trinets are phylogenetic networks with two three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 network displaying given set $$\mathbb {T}$$ binets or over taxon X, constructing such whenever it exists. We show that this is NP-hard for but polynomial-time solvable binets. Moreover, still inputs consisting as long cycles in have size three. Finally, present an $$O(3^{|X|} poly(|X|))$$ time algorithm general sets trinets. The latter...
Phylogenetic networks are a generalization of evolutionary trees that can be used to represent reticulate processes such as hybridization and recombination. Here, we introduce new approach called TriLoNet (Trinet Level- one Network algorithm) construct directly from sequence alignments which works by piecing together smaller phylogenetic networks. More specifically, using bottom up similar Neighbor-Joining, constructs level-1 (networks somewhat more general than trees) on three taxa. In...
Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which case, for instance, in presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need be modified order applicable networks. In this paper, we discuss two definitions on networks, "hardwired" and "softwired," examine complexity computing them given a network topology character. By exploiting link with problem...
We show that the problem of computing hybridization number two rooted binary phylogenetic trees on same set taxa $X$ has a constant factor polynomial-time approximation if and only minimum-size feedback vertex in directed graph (DFVS) approximation. The latter problem, which asks for minimum vertices to be removed from transform it into acyclic graph, is one problems Karp's seminal 1972 list 21 NP-complete problems. Despite considerable attention combinatorial optimization community, remains...
Phylogenetic networks are a generalization of evolutionary trees and an important tool for analyzing reticulate histories. Recently, there has been great interest in developing new methods to construct rooted phylogenetic networks, that is, whose internal vertices correspond hypothetical ancestors, leaves sampled taxa, which with more than one parent taxa formed by events such as recombination or hybridization. Several constructing use the strategy building up tree from simpler blocks (such...