Carnegie Mellon University
April 03, 2018

Kingsford Group has 2 ISMB 2018 Papers Accepted

Multiple members of Carl Kingsford’s group have had their papers accepted to ISMB 2018.

Carl Kingsford Natalie Sauerwald Dan DeBlasio scs_comp-bio_guillaume-marcais_2017_002.jpg
Carl Kingsford Natalie Sauerwald Dan DeBlasio Guillaume Marcais

Natalie Sauerwald and Carl Kingsford’s paper titled Quantifying the similarity of topological domains across normal and cancer human cell types discusses “three-dimensional chromosome structure has been increasingly shown to influence various levels of cellular and genomic functions. Through Hi-C data, which maps contact frequency on chromosomes, it has been found that structural elements termed topologically associating domains (TADs) are involved in many regulatory mechanisms. However, we have little understanding of the level of similarity or variability of chromosome structure across cell types and disease states. In this work we present a method to quantify resemblance and identify structurally similar regions between any two sets of TADs. We present an analysis of 23 human Hi-C samples representing various tissue types in normal and cancer cell lines. We quantify global and chromosome-level structural similarity, and compare the relative similarity between cancer and non-cancer cells. We find that cancer cells show higher structural variability around commonly mutated pan-cancer genes than normal cells at these same locations. Software for the methods and analysis can be found at

The second paper, authored by Guillaume Marçais, Dan DeBlasio and Carl Kingsford, is titled Asymptotically optimal minimizers schemes. “The minimizers technique is a method to sample k-mers that is used in many bioinformatics software to reduce computation, memory usage and run time. The number of applications using minimizers keeps on growing steadily. Despite its many uses, the theoretical understanding of minimizers is still very limited. In many applications, selecting as few k-mers as possible (i.e.\ having a low density) is beneficial. The density is highly dependent on the choice of the order on the k-mers. Different applications use different orders, but none of these orders are optimal. A better understanding of minimizers schemes, and the related local and forward schemes, will allow designing schemes with lower density, and thereby making existing and future bioinformatics tools even more efficient. From the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare k-mers. These orders are the first known orders that are asymptotically optimal. Additionally, we give improved bounds on the density achievable by the 3 type of schemes.”

Congratulations to the Kingsford Group!