Carl Kingsford Assistant Professor Department of Computer Science, UM Institute for Advanced Computer Studies, and Center for Bioinformatics and Computational Biology Ph.D., Princeton University, 2005 (advisor: Mona Singh) MA, Princeton University, 2002 BS, Duke University, 2000 carlk [at] umiacs.umd.edu Center for Bioinformatics and Computational Biology Biomolecular Sciences Bldg #296 College Park, MD 20742 301-405-7395

Office Hours: Tuesday 2:00-3:30 in AVW 3223.

• Fall 2009 - Networks Algorithms for Biology (CMSC 858L)
• Fall 2009 - Design & Analysis of Computer Algorithms (CMSC 451)
• Spring 2009 - Graphs and Networks in Computational Biology (CMSC 858L)
• Fall 2008 - Design & Analysis of Computer Algorithms (CMSC 451)
• Spring 2008 - Data Structures (CMSC 420)
• Fall 2007 - Graphs and Networks in Computational Biology (CMSC 858L)

In general, we are interested in designing graph algorithms to extract insight from biological data.

Protein interactions and networks:

• Clustering within protein-protein interaction networks.
• Protein function prediction.
• Protein structure prediction (e.g. using mathematical programming to predict protein structure).

Bacterial & viral genome analysis:

• Overlapping genes in Bacteria.
• Transcription termination in bacteria. See the TransTermHP program for predicting Rho-independent terminators.
• Reassortment in the influenza genome.

Click on the title of the paper to download a PDF version.
* indicates that the authors are alphabetized.
† indicates equal contribution.

• S. Navlakha and C. Kingsford. Exploring Biological Network Dynamics with Ensembles of Graph Partitions. To appear in Pac. Symp. Biocomp. 2010.
• C. Kingsford* and G. Marçais.* A synthesis for exactly 3-edge-connected graphs. In submission. [Preprint]
• C. Kingsford* and G. Marçais.* Vertices of degree k in edge-minimal, k-edge-connected graphs. In submission. [Preprint]
• C. Kingsford†, N. Nagarajan†, and S. L. Salzberg. 2009 Swine-Origin Influenza A (H1N1) Resembles Previous Influenza Isolates. PLoS ONE 4(7):e6402, 2009.
• S. Navlakha, J. White, N. Nagarajan, M. Pop, and C. Kingsford. Finding Biologically Accurate Clusterings in Hierarchical Tree Decompositions Using the Variation of Information. In Proceedings of RECOMB 2009, Lectures Notes in Computer Science 5541, pages 400-417. [Preprint]
• G. Lapizco-Encinas, C. Kingsford, and J. Reggia. A Cooperative Combinatorial Particle Swarm Optimization for Side-chain Packing. Proceedings of IEEE Swarm Intelligence Symposium 2009, pages 22-29. [Preprint]
• S. Navlakha, M. Schatz, and C. Kingsford. Revealing Biological Modules via Graph Summarization. Presented at RECOMB-SB/RG/DREAM3 satellite conference, 2008. Journal version J. Comp. Biol. 16(2):253-264, 2009. [Preprint] [Video of RECOMB-SB Talk]
• C. Kingsford and S. L. Salzberg. What are decision trees? Nature Biotechnology 26:1011-1013 (2008).
• N. Nagarajan and C. Kingsford. Uncovering Genomic Reassortments Among Influenza Strains by Enumerating Maximal Bicliques. In Proceedings of IEEE International Conference on Bioinformatics and Biomedicine, pages 223-230, 2008. [Preprint]
• C. Kingsford, A. Delcher, S. Salzberg. A Unified Model Explaining the Offsets of Overlapping and Near-Overlapping Prokaryotic Genes. Molecular Biology and Evolution, 24(9):2091–2098 (2007). (Journal Page)
• S. Salzberg, C. Kingsford, G. Cattoli, D.J. Spiro, D.A. Janies, M.M. Aly et al. Genome analysis linking recent European and African influenza (H5N1) viruses. Emerging Infectious Diseases 13(5), 2007
• C. Kingsford, K. Ayanbule, and S. Salzberg. Rapid, accurate, computational discovery of Rho-independent transcription terminators illuminates their relationship to DNA uptake. Genome Biology 8:R22 (2007). [Preprint] [Software Download]
• C. Kingsford, E. Zaslavsky, and M. Singh. A compact mathematical programming formulation for DNA motif finding. In the proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (2006). [PDF of Talk Slides] [Preprint]
• C. Kingsford, B. Chazelle, and M. Singh. Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics 21(7):1028-1039 (2005). (Advanced access publication on 11/16/2004.) [Preprint] [Software Download]
• B. Chazelle, C. Kingsford, and M. Singh. A semidefinite programming approach to side-chain positioning with new rounding strategies. INFORMS Journal on Computing, Special Issue on Computational Molecular Biology/Bioinformatics, 16:380-392 (2004). [Preprint]

Students

• Guillaume Marçais (co-advised with Jim Yorke)
• Saket Navlakha

• Grecia Lapizco-Encinas (co-advised with Jim Reggia; now a postdoc in Dept. of Computer Science at the Universidad Carlos III de Madrid)