A Journey with Symbolic Interaction

In this cranky and arrogant chapter I consider several aspects of my use of symbolic interactionist perspectives on my research and thinking. The following are the elements of the chapter: (1) the historical context of my initial encounter with symbolic interactionism (SI); (2) my interpretation of key ideas of SI; (3) its relation to specific research of mine; (4) the relation of other perspectives to my research; and (5) some critiques of SI. I conclude with a truncated discussion of my dissatisfaction with the overtheorizing and overscientizing of sociology. Seeking balance, I end with predictions of a grand and glorious future.     

A new recombination lower bound and the minimum perfect phylogenetic forest problem

Understanding recombination is a central problem in population genetics. In this paper, we address an established computational problem in this area: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences (Hudson and Kaplan in Genetics 111, 147–164, 1985; Myers and Griffiths in Genetics 163, 375–394, 2003; Gusfield et al. in Discrete Appl. Math. 155, 806–830, 2007; Bafna and Bansal in IEEE/ACM Trans. Comput. Biol. Bioinf. 1, 78–90, 2004 and in J. Comput. Biol. 13, 501–521, 2006; Song et al. in Bioinformatics 421, i413–i244, 2005). In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated as the minimum perfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound (Myers and Griffiths in Genetics 163, 375–394, 2003), a very good lower bound in practice (Song et al. in Bioinformatics 421, i413–i422, 2005). We prove that, like several other lower bounds (Bafna and Bansal in J. Comput. Biol. 13, 501–521, 2006), computing the forest bound is NP-hard. Finally, we describe an integer linear programming (ILP) formulation that computes the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing lower bounds for low quality data. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 16–26. The work was performed while Y. Wu was with UC Davis and supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation. D. Gusfield supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation.