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

Contact Information

carlk [at] umiacs.umd.edu

Center for Bioinformatics and Computational Biology
Biomolecular Sciences Bldg #296
College Park, MD 20742
301-405-7395

Open Positions (March 2012)

I have an open position for a postdoc interested in working on optimization algorithms for biological problems. Potential projects include reconstruction of the evolutionary history of the influenza virus and biological network design under various models evolution, among others.

Please email me your CV with subject line "Postdoc Application" if you are interested.

Current Research Interests

We are interested in designing graph and optimization algorithms to extract insight from biological data. In particular, we focus on the following classes of problems:

Protein interactions and networks: Clustering within networks; protein function prediction; protein structure prediction; evolution of interactions. This work is supported by NSF grant 0849899 and NSF grant CCF-1053918 (CAREER award).
Bacterial genome analysis: Overlapping genes in bacteria; transcription termination in bactera (See the TransTermHP program for predicting Rho-independent terminators). This work is supported by NSF grant IIS-0812111. (PI: Mihai Pop)
Viral evolution: Reassortment in the influenza genome. This work is supported by NIH grant 1R21AI085376
Chromosome structure prediction. Algorithms for determining the spatial organization of eukaryotic genomes from Chromosome Conformation Capture data. Supported by a UMIACS New Research Frontiers Award.

Software

Many of the papers listed below contain links to websites that offer the software used in the experiments described in the paper. Here are some additional software packages:

CORAL - system for interactive visualizations of differences between clusterings.
Map of Jazz Musicians - web application to explore recorded collaborations between jazz musicians.
GIRAF - find reassortments in collections of influenza genome sequences.
JELLYFISH - count k-mers in large sequence databases very fast.
PARANA - parsimonious reconstruction of ancestral interaction networks.
GHOST - Global alignment between two graphs.
STARFISH - Identify rigid components with the pebble game and a body-bar-and-hinge reduction
TransTermHP - find rho-independent transcription terminators in bacterial genomes.
Network Archaeology - infer evolutionary history of a network.
VI-Cut - find clustering that best matches imperfectly-known cluster hints.

Teaching

A collection of bioinformatics lectures and computer science background lectures can be found here.

Group Members

Current:

Geet Duggal (co-advised with Michelle Girvan)
Darya Filippova
Rob Patro
Emre Sefer
Praveen Vaddadi (co-advised with Sridhar Hannenhalli)
Hao Wang
Jeremy Bellay (postdoc)

Former Students:

Grecia Lapizco-Encinas, Ph.D. (co-advised with Jim Reggia; first position after graduation: postdoc in Dept. of Computer Science at the Universidad Carlos III de Madrid)
Saket Navlakha, Ph.D. (defended Oct. 29, 2010; "Algorithms to Explore the Structure and Evolution of Biological Networks")
Guillaume Marçais, Ph.D. (co-advised with Jim Yorke; defended July 25, 2011)

Selected Publications

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

Biological Network Analysis

R. Patro and C. Kingsford. Global network alignment using multiscale spectral signatures. Under review. [preprint]
G. Duggal and C. Kingsford. Graph rigidity reveals non-deformable collections of chromosome conformation constraints. Under review. [preprint] [PSB 2012 presentation]
R. Patro, E. Sefer, J. Malin, G. Marçais, S. Navlakha, and C. Kingsford. Parsimonious Reconstruction of Network Evolution. In WABI 2011, LNCS 6833, pages 237-249. [software]
E. Sefer and C. Kingsford. Metric Labeling and Semi-metric Embedding for Protein Annotation Prediction. In RECOMB 2011, pages 392-407.
R. Patro and C. Kingsford. Learning from Diversity: Epitope Prediction with Sequence and Structure Features using an Ensemble of Support Vector Machines. Winner, DREAM5 Challenge 1 competition. Presented at RECOMB Systems Biology Satellite Conference.
S. Navlakha and C. Kingsford. Network Archaeology: Uncovering Ancient Networks from Present-day Interactions. PLoS Computational Biology 7(4): e1001119. doi:10.1371/journal.pcbi.1001119. [Website]
G. Duggal, S. Navlakha, M. Girvan, and C. Kingsford. Uncovering Many Views of Biological Networks Using Ensembles of Near-Optimal Partitions. In MultiClust: 1st International Workshop on Discovering, Summarizing and Using Multiple Clusterings at KDD 2010. [Website]
S. Navlakha and C. Kingsford. The Power of Protein Interaction Networks for Associating Genes with Diseases. Bioinformatics, 2010; doi: 10.1093/bioinformatics/btq076. Recommended by the Faculty of 1000 [Website]
D. E. Kelley and C. Kingsford. Extracting between-pathway models from E-MAP interactions using expected graph compression. In RECOMB 2010, Lecture Notes in Computer Science, Volume 6044/2010, pp. 248-262. Journal version in J. Comp. Biol. 18(3):379-390, 2011.
S. Navlakha and C. Kingsford. Exploring Biological Network Dynamics with Ensembles of Graph Partitions. In Proceedings of Pac. Symp. Biocomp. 2010, pages 166-177.
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] Journal version in J. Comp. Biol. 17(3):503-516, 2010 [Website]
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]

Bacterial (and Other) Genomics

G. Marçais and C. Kingsford. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics, 2011. [Software]
J. Wetzel, C. Kingsford, and M. Pop. Assessing the benefits of using mate-pairs to resolve repeats in de novo short-read assemblies. BMC Bioinformatics 12:95, 2011.
J. R. White, S. Navlakha, N. Nagarajan, M. Ghodsi, C. Kingsford, and M. Pop. Alignment and clustering of phylogenetic markers - implications for microbial diversity studies. BMC Bioinformatics 2010, 11:152.
C. Kingsford, M. C. Schatz, and M. Pop. Assembly complexity of prokaryotic genomes using short reads. BMC Bioinformatics 11:21, 2010. (Top 10 most-viewed articles Jan/Feb 2010. Top-10 cited article in BMC Bioinformatics for 2010)
C. Kingsford, A. Delcher, and 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)
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] (cited > 71 times)
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] Journal version J. Discrete Algorithms 9(4):326-334 (2011).

Influenza Evolution

N. Nagarajan and C. Kingsford. GiRaF: Robust, Computational Identification of Influenza Reassortments via Graph Mining. Nuc. Acids Res., 39(6):e34, 2011.
C. Kingsford†, N. Nagarajan†, and S. L. Salzberg. 2009 Swine-Origin Influenza A (H1N1) Resembles Previous Influenza Isolates. PLoS ONE 4(7):e6402, 2009. (cited > 21 times)
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]
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. (cited > 87 times)

Protein Structure (generally older work)

G. Lapizco Encinas, Carl Kingsford, and James Reggia. Particle Swarm Optimization for Multimodal Combinatorial Problems and its application to Protein Design. In IEEE Congress on Evolutionary Computation, 2010.
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]
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] (cited > 46 times)
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] (cited > 23 times)

Other Papers

C. Kingsford* and G. Marçais.* A synthesis for exactly 3-edge-connected graphs. [Preprint]
C. Kingsford* and G. Marçais.* Vertices of degree k in edge-minimal, k-edge-connected graphs. [Preprint]
C. Kingsford and S. L. Salzberg. What are decision trees? Nature Biotechnology 26:1011-1013 (2008).

Awards

2008 - Named one of 30 “Tomorrow's PIs” by Genome Technology Magazine
2010 - UMD Department of Computer Science "Teaching Excellence Award for a Professor"
2011 - NSF CAREER Award
2012 - Alfred P. Sloan Research Fellow