- April 2016: 14% of RECOMB 2016 papers involve either a current or fomer group member! Congrats to all.
- February 2016: Our sequence search technique was published.
- September 9, 2015: Brad Solomon, a Ph.D. student in the Kingsford group, has been awarded a Richard King Mellon Foundation Presidential Fellowship in the Life Sciences by Carnegie Mellon University for his work in computational genomics. With this award, Brad joins the inaugural class of CMU Presidential Fellows.
- August 2, 2015: Armatus selected for highlights presentation at ACM-BCB.
- July 23, 2015: Darya Filippova sucessfully defends her Ph.D. dissertation. Congratulations!
- April 20, 2015: Former group member Saket Navlakha selected to attend the Heidelberg Laureate Forum.
- April 2015: Former group member Rob Patro gives RECOMB highlight talk on Sailfish in Poland.
- April 2015: Recently graduated Ph.D. student Emre Sefer presents paper at RECOMB 2015.
- April 2015: Emre Sefer presents paper at ICDE in Korea.
- February 2015: Emre Sefer successfully defends his Ph.D. thesis!
- December 2014: Geet Duggal successfully defends his Ph.D. thesis!
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:
- Genomics & genome assembly: RNA-seq expression quantification; genome assembly; large-scale sequence search, etc. This work is currently supported by NIH grant 1R21HG006913, NSF grant CCF-1319998, and a Data-Driven Invesgator grant from the Gordon and Betty Moore Foundation.
- Chromatin structure and function: Algorithms for determining the spatial organization of eukaryotic genomes from Chromosome Conformation Capture data. Supported by NIH grant R01HG007104.
- Viral evolution: Reassortment in the influenza genome. This work was supported by NIH grant 1R21AI085376.
- Protein interactions and networks: Evolution of interactions; protein function prediction; clustering within networks; protein structure prediction. This work was supported by NSF grant EF-0849899 and by NSF grant CCF-1053918/CCF-1256087 (CAREER award).
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.
Fall 2015: Algorithms and Advanced Data Structures
Fall 2015: Programming for Scientists
Fall 2014: Algorithms and Advanced Data Structures
Fall 2014: Programming for Scientists
Spring 2014: Algorithms & Data Structures for Scientists
Fall 2013: String Algorithms
Selected Publications ⇡
* indicates alphabetized authors. † indicates equal contribution.
- Nitish Gupta, Komal Sanjeev, Tim Wall, Carl Kingsford, Rob Patro. Efficient Index Maintenance Under Dynamic Genome Modification. Presented at RECOMB-seq 2016 satellite conference.
- Rob Patro, Geet Duggal, and Carl Kingsford. Salmon: Ultrafast, Accurate and Versatile Quantification from RNA-seq Data using Lightweight Alignment
- Hao Wang, Joel McManus, Carl Kingsford. Isoform-level Ribosome Occupancy Estimation Guided by Transcript Abundance with Ribomap Bioinformatics (2016). [Preprint]
- Brad Solomon and Carl Kingsford. Fast search of thousands of short-read sequencing experiments, Nature Biotechnology (2016). [Preprint]
- Hao Wang, Joel McManus and Carl Kingsford. Accurate Recovery of Ribosome Positions Reveals Slow Translation of Wobble-Pairing Codons in Yeast. To appear in RECOMB 2016.
- David Pellow, Darya Filippova and Carl Kingsford. Improving Bloom filter performance on sequence data using k-mer Bloom filters. To appear in RECOMB 2016.
- Darya Filippova and Carl Kingsford. Rapid Separable Compression Enables Fast Analyses of Sequence Alignments. To appear in ACM-BCB 2015.
- E. Sefer and C. Kingsford. Semi-nonparametric Modeling of Topological Domain Formation From Epigenetic Data. To appear in WABI 2015.
- R. Patro and C. Kingsford. Data-dependent bucketing improves reference-free compression of sequencing reads Bioinformatics 2015.
- C. Kingsford and R. Patro. Reference-based compression of short-read sequences using path encoding. Bioinformatics 2015; doi: 10.1093/bioinformatics/btv071
- E. Sefer, G. Duggal, and C. Kingsford. Deconvolution Of Ensemble Chromatin Interaction Data Reveals The Latent Mixing Structures In Cell Subpopulations. To appear in RECOMB 2015.
- H Xin, J Greth, J Emmons, G Pekhimenko, C Kingsford, Can Alkan, Onur Mutlu. Shifted Hamming Distance: A Fast and Accurate SIMD-Friendly Filter to Accelerate Alignment Verification in Read Mapping Bioinformatics 2015; doi: 10.1093/bioinformatics/btu856
- R. Patro, S. M. Mount, and Carl Kingsford. Sailfish enables alignment-free isoform quantification from RNA-seq reads using lightweight algorithms. Nature Biotechnology (2014). doi:10.1038/nbt.2862.
- G Duggal, H Wang, and Carl Kingsford. Higher-order chromatin domains link eQTLs with the expression of far-away genes. Nucleic Acids Research 2013; doi: 10.1093/nar/gkt857
- H. Wang, G. Duggal, R. Patro, M. Girvan, S. Hannenhalli, and C. Kingsford. Topological properties of chromosome conformation graphs reflect spatial proximities within chromatin. To appear in ACM BCB 2013.
- D. Fillipova†, R. Patro†, G. Duggal†, and C. Kingsford. Identification of alternative topological domains in chromatin Algorithms for Molecular Biology.2014, 9:14 DOI: 10.1186/1748-7188-9-14 (conference version in WABI 2013).
- G. Duggal and C. Kingsford. Graph rigidity reveals well-constrained regions of chromosome conformation embeddings. 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.
- 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†, 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.
- 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).
Biological Network Analysis
- R Patro, R Norel, et al. A computational method for designing diverse linear epitopes including citrullinated peptides with desired binding affinities to intravenous immunoglobulin. BMC Bioinformatics 2016. (This reports on the winning system in the DREAM5 Challenge 1 competition, and was originally presented at the RECOMB Systems Biology satellite conference.)
- E. Sefer and Carl Kingsford. Convex Risk Minimization To Infer Networks From Probabilistic Diffusion Data At Multiple Scales. To appear in ICDE 2015.
- E. Sefer and Carl Kingsford. Diffusion Archaeology for Diffusion Progression History Reconstruction. To appear in ICDM 2014.
- R. Patro and C. Kingsford. Predicting protein interactions via parsimonious network history inference. 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 28(23):3105-3114 (2012).
- 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.
- N. Nagarajan and C. Kingsford. GiRaF: Robust, Computational Identification of Influenza Reassortments via Graph Mining. Nuc. Acids Res., 39(6):e34, 2011.
- 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]
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]
- 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