Who is Who in Phylogenetic Networks

Publications related to 'bound'   Order by:   Type | Year

Only And Or     related to:

Associated keywords

agreement-forest ARG bound distance-between-networks dynamic-programming explicit-network from-binary-characters from-clusters from-network from-rooted-trees galled-network heuristic hybridization LST-distance minimum-number nearly-stable-network NNI-distance NNI-moves phylogenetic-network phylogeny polynomial Program-PIRN recombination reconstruction reticulation-visible-network software SPR-distance stable-child-network TBR-distance

Article (Journal)

1 Vineet Bafna and Vikas Bansal. The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds. In TCBB, Vol. 1(2):78-90, 2004. Keywords: ARG, bound, minimum number, phylogeny, recombination. Note: http://www-cse.ucsd.edu/users/vbafna/pub/tcbb04.pdf.         Toggle abstract "We consider the following problem: Given a set of binary sequences, determine lower bounds on the minimum number of recombinations required to explain the history of the sample, under the infinite-sites model of mutation. The problem has implications for finding recombination hotspots and for the Ancestral Recombination Graph reconstruction problem. Hudson and Kaplan gave a lower bound based on the four-gamete test. In practice, their bound R m often greatly underestimates the minimum number of recombinations. The problem was recently revisited by Myers and Griffiths, who introduced two new lower bounds R h and R s which are provably better, and also yield good bounds in practice. However, the worst-case complexities of their procedures for computing R h and R s are exponential and super-exponential, respectively. In this paper, we show that the number of nontrivial connected components, Rc, in the conflict graph for a given set of sequences, computable in time O(nm 2), is also a lower bound on the minimum number of recombination events. We show that in many cases, R c is a better bound than R h. The conflict graph was used by Gusfield et al. to obtain a polynomial time algorithm for the galled tree problem, which is a special case of the Ancestral Recombination Graph (ARG) reconstruction problem. Our results also offer some insight into the structural properties of this graph and are of interest for the general Ancestral Recombination Graph reconstruction problem." 2 Mihaela Baroni, Stefan Grünewald, Vincent Moulton and Charles Semple. Bounding the number of hybridization events for a consistent evolutionary history. In JOMB, Vol. 51(2):171-182, 2005. Keywords: agreement forest, bound, explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BGMS05.pdf.         Toggle abstract "Evolutionary processes such as hybridisation, lateral gene transfer, and recombination are all key factors in shaping the structure of genes and genomes. However, since such processes are not always best represented by trees, there is now considerable interest in using more general networks instead. For example, in recent studies it has been shown that networks can be used to provide lower bounds on the number of recombination events and also for the number of lateral gene transfers that took place in the evolutionary history of a set of molecular sequences. In this paper we describe the theoretical performance of some related bounds that result when merging pairs of trees into networks. © Springer-Verlag 2005." 3 Lavanya Kannan, Hua Li and Arcady Mushegian. A Polynomial-Time Algorithm Computing Lower and Upper Bounds of the Rooted Subtree Prune and Regraft Distance. In JCB, Vol. 18(5):743-757, 2011. Keywords: bound, minimum number, polynomial, SPR distance. Note: http://dx.doi.org/10.1089/cmb.2010.0045.         Toggle abstract "Rooted, leaf-labeled trees are used in biology to represent hierarchical relationships of various entities, most notably the evolutionary history of molecules and organisms. Rooted Subtree Prune and Regraft (rSPR) operation is a tree rearrangement operation that is used to transform a tree into another tree that has the same set of leaf labels. The minimum number of rSPR operations that transform one tree into another is denoted by drSPR and gives a measure of dissimilarity between the trees, which can be used to compare trees obtained by different approaches, or, in the context of phylogenetic analysis, to detect horizontal gene transfer events by finding incongruences between trees of different evolving characters. The problem of computing the exact d rSPR measure is NP-hard, and most algorithms resort to finding sequences of rSPR operations that are sufficient for transforming one tree into another, thereby giving upper bound heuristics for the distance. In this article, we present an O(n4) recursive algorithm D-Clust that gives both lower bound and upper bound heuristics for the distance between trees with n shared leaves and also gives a sequence of operations that transforms one tree into another. Our experiments on simulated pairs of trees containing up to 100 leaves showed that the two bounds are almost equal for small distances, thereby giving the nearly-precise actual value, and that the upper bound tends to be close to the upper bounds given by other approaches for all pairs of trees. © Copyright 2011, Mary Ann Liebert, Inc. 2011." 4 Katharina Huber, Simone Linz, Vincent Moulton and Taoyang Wu. Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations. In JOMB, Vol. 72(2):699-725, 2016. Keywords: bound, distance between networks, from network, LST distance, phylogenetic network, phylogeny.         5 Sajad Mirzaei and Yufeng Wu. Fast Construction of Near Parsimonious Hybridization Networks for Multiple Phylogenetic Trees. In TCBB, Vol. 13(3):565-570, 2016. Keywords: bound, explicit network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program PIRN, reconstruction, software. Note: http://www.engr.uconn.edu/~ywu/Papers/PIRNs-preprint.pdf.         6 Andrew R. Francis, Katharina Huber, Vincent Moulton and Taoyang Wu. Bounds for phylogenetic network space metrics. In JOMB, Vol. 76(5):1229-1248, 2018. Keywords: bound, distance between networks, from network, NNI distance, NNI moves, phylogenetic network, phylogeny, SPR distance, TBR distance. Note: https://arxiv.org/abs/1702.05609.

InProceedings

7 Vineet Bafna and Vikas Bansal. Improved recombination lower bounds for haplotype data. In RECOMB05, Vol. 3500:569-584 of LNCS, springer, 2005. Keywords: bound, minimum number, phylogeny, recombination. Note: http://www.cse.ucsd.edu/users/vbafna/pub/recomblb05.pdf.         8 Hyun Jung Park, Guohua Jin and Luay Nakhleh. Algorithmic strategies for estimating the amount of reticulation from a collection of gene trees. In CSB10, 2010. Keywords: bound, from rooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/ParkEtAl-CSB2010.pdf.

MastersThesis

9 Julia Matsieva. A Static Formulation of the History Bound Problem. Master's thesis, UC Davis, 2014. Keywords: bound, dynamic programming, explicit network, from binary characters, from clusters, phylogenetic network, phylogeny, polynomial. Note: https://escholarship.org/uc/item/3741t064.

Misc

10 Andreas Gunawan and Louxin Zhang. Bounding the Size of a Network Defined By Visibility Property. 2015. Keywords: bound, explicit network, galled network, nearly-stable network, phylogenetic network, phylogeny, reticulation-visible network, stable-child network. Note: http://arxiv.org/abs/1510.00115.