Who is Who in Phylogenetic Networks

Publications of Vineet Bafna     Order by:   Type | Year

Associated keywords

ARG bound explicit-network from-sequences galled-tree minimum-number phylogenetic-network phylogeny Program-Beagle Program-GalledTree recombination reconstruction software

Article (Journal)

1 Dan Gusfield, Vikas Bansal, Vineet Bafna and Yun S. Song. A Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In JCB, Vol. 14(10):1247-1272, 2007. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, Program Beagle, Program GalledTree, recombination, reconstruction, software. Note: http://www.eecs.berkeley.edu/~yss/Pub/decomposition.pdf.         2 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."

InProceedings

3 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.