Personalia
Devdatt Dubhashi. Born in New Delhi, India, in 1965. Ph.D. from Cornell University, Ithaca, NY. Professor of Computing Science at Chalmers University of Technology, Sweden.
Theme Group Fellow (1 September – 31 October 2015)
Algorithms for Inferring Linguistic Phylogenies
Research Question
How can the algorithmic problems in the theme group’s project, be solved?
Project Description
I propose to take the lead on the algorithmic problems in the theme group research proposal. A number of topics my research group in Algorithms/Bioinformatics has covered are directly applicable to the problems described in the main proposal: i) Variable-order Markov models of genomic signatures (Dalevi et al. 2006) appear to be applicable to the study of horizontal transfer in linguistics, and, ii) approximate Bayesian Computation (ABC) is a mathematically sound approach towards a tractable tree space search. Accurate deployment of ABC requires both expertise on the theory of ABC (Christos Dimitrakakis in my research group is an expert) and familiarity with the specific Markoc Chain Monte Carlo algorithm used (which is found in the proposed theme group). Other problems addressed in the proposed theme group require more re-examination. The typical phylogenetic problem of inferring a tree with branch lengths given character data input can be decomposed into finding the correct tree topology and finding the branch lengths. These two problems can further be decomposed by natural assumptions on, e.g., the bounds of accelerated change, into an (easier) version with constraints and one unconstrained, where the algorithm differs between the two. It is possible that there are extant approximation algorithms that fit various constrained versions of the phylogenetic inference problem that then come with theoretically sound guarantees on either computation time or output error.
Selected Publications
1. D.P. Dubhashi and D. Ranjan, “Balls and Bins: A Study in Negative Dependence”, Random Structures and Algorithms, 13(2), pp. 99-124 1998.
2. Dubhashi, Devdatt; Mei, Alessandro; Panconesi, Alessandro; Radhakrishnan, Jaikumar; Srinivasan, Aravind, “ Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons”, J. Comp. Systems Sciences, 71,467-479, 2005.
3. P. Norberg, M. Bergstrom, V. Jethava, D. Dubhashi, and M. Hermansson, “The IncP-1 plasmid backbone adapts to different host bacterial species and evolves through homologous recombination,” Nature Commun, vol. 2, 2011