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: Evolution of interactions; protein function prediction; clustering within networks; protein structure prediction. This work is supported by NSF grant EF-0849899 and by NSF grant CCF-1053918/CCF-1256087 (CAREER award).
• Genomics & genome assembly: RNA-seq expression quantification; genome assembly; overlapping genes in bacteria; transcription termination in bacteria (See the TransTermHP program for predicting Rho-independent terminators). This work was supported by NSF grant IIS-0812111. (PI: Mihai Pop) and currently by NIH grant 1R21HG006913.
• Viral evolution: Reassortment in the influenza genome. This work is supported by NIH grant 1R21AI085376.
• Chromatin structure and function: Algorithms for determining the spatial organization of eukaryotic genomes from Chromosome Conformation Capture data. (Previously supported by a UMIACS New Research Frontiers Award.)

Teaching

Here is a collection of lecture slides about bioinformatics and some relevant computer science background.

Webpages for specific recent courses can be found in the Teaching section.

Next Semester (Fall 2013): String Algorithms

This Semester (Spring 2013): Algorithms & Data Structures (for Scientists) and Bioinformatics Data Integration Practicum

Selected Publications ⇡

^* indicates alphabetized authors. ^† indicates equal contribution.

Biological Network Analysis

• R. Patro and C. Kingsford. Predicting protein interactions via parsimonious network history inference. To appear in ISMB/ECCB 2013.
• D. Filippova, A. Gadani, and C. Kingsford. Coral: an integrated suite of visualizations for comparing clusterings. BMC Bioinformatics 13:276, 2012. [Software]
• R. Patro and C. Kingsford. Global network alignment using multiscale spectral signatures. Bioinformatics.
• G. Duggal and C. Kingsford. Graph rigidity reveals non-deformable collections of chromosome conformation constraints. BMC Bioinformatics 13:241, 2012. [PSB 2012 presentation]
• G. Duggal, R. Patro, E. Sefer, H. Wang, D. Filippova, S. Khuller, and C. Kingsford. Resolving Spatial Inconsistencies in Chromosome Conformation Data. In WABI 2012. Lecture Notes in Computer Science, 2012, Volume 7534/2012, 288-300,
• D. Filippova, M. Fitzgerald, C. Kingsford and F. Benadon. Dynamic exploration of recording sessions between jazz musicians over time. To appear in SocialCom 2012 [software]
• R. Patro^†, G. Duggal^†, E. Sefer, H. Wang, D. Filippova, and C. Kingsford. The Missing Models: A Data-Driven Approach for Learning How Networks Grow. In KDD pp. 42-50, 2012. [Teaser Video] Won best video at KDD.
• 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. Journal version in Algorithms for Molecular Biology 2012, 7:25. [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]
• 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.
• 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.

Protein Structure (generally older work)

• G. Lapizco Encinas, C. Kingsford, and J. 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]
• 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]

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