Prashant Pandey, Yinjie Gao, and Carl Kingsford (2019) VariantStore: A Large-Scale Genomic Variant Search Index. Genome Biology *22*: 231 (2021).

The ability to efficiently query genomic variation data from thousands of samples is critical to achieve the full potential of many medical and scientific applications such as personalized medicine. We present VariantStore, a system for efficiently indexing and searching millions of genomic variants across thousands of samples.

Cong Ma and Carl Kingsford (2019) Estimating mutual information under measurement error. bioRxiv 852384.

Mutual information is widely used to characterize dependence between biological signals, such as co-expression between genes or co-evolution between amino acids. However, measurement error of the biological signals is rarely considered in estimating mutual information. Measurement error is widespread and non-negligible in some cases.

November 10, 2019 — Congratulations to Natalie Sauerwald, 5th-year CPCB Ph.D. student, for having one of her papers:

N Sauerwald and C Kingsford. Quantifying the similarity of topological domains across normal and cancer human cell types, Bioinformatics (ISMB) 34(13):i475-i483 (2018).

selected as one of the “Top 10 Reading Papers“ at RECOMB/ISCB Regulatory & Systems Genomics 2019.

The paper developed a method to compare genome structure

View source

Natalie Sauerwald and Carl Kingsford (2019) A statistical method for identifying consistently important features across samples. BioRxiv.

In many applications, features with consistently high measurements across many samples are particularly meaningful and useful for quality control or biological interpretation. Identification of these features among many others can be challenging especially when the samples cannot be expected to have the same distribution or range of values.

Cong Ma and Carl Kingsford (2019) Detecting, categorizing, and correcting coverage anomalies of RNA-seq quantification. Cell Systems *9*:1-11.

Due to incomplete reference transcriptomes, incomplete sequencing bias models, or other modeling defects, algorithms to infer isoform expression from RNA-seq sometimes do not accurately model expression. We present a computational method to detect instances where a quantification algorithm could not completely explain the input reads. Our approach identifies regions where the read coverage significantly deviates from expectation.

HuBMAP Consortium (2019) The human body at cellular resolution: the NIH Human Biomolecular Atlas Program. Nature *574*:187-192 (2019).

Transformative technologies are enabling the construction of three-dimensional maps of tissues with unprecedented spatial and molecular resolution.

September 10, 2019 — The paper ‘Practical Universal k-mer Sets for Minimizer Schemes’, was awarded best student paper at the ACM-BCB 2019 conference in Niagara Falls, NY.

Scott A. Keith, Rory Eutsey, Heewook Lee, Brad Solomon, Stacie Oliver, Carl Kingsford, N. Luisa Hiller, and Brooke M. McCartney (2019) Identification of Microbiota-Induced Gene Expression Changes in the Drosophila melanogaster Head. bioRxiv.

Symbiotic microorganisms exert multifaceted impacts on the physiology of their animal hosts. Recent discoveries have shown the gut microbiota influence host brain function and behavior, but the host and microbial molecular factors required to actuate these effects are largely unknown.

Yutong Qiu, Cong Ma, Han Xie, and Carl Kingsford (2019) Detecting Transcriptomic Structural Variants in Heterogeneous Contexts via the Multiple Compatible Arrangements Problem. 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) 18:1--18:19 (2019); journal version in Alg Mol Bio (2020).

Transcriptomic structural variants (TSVs) --- structural variants that affect expressed regions --- are common, especially in cancer. Detecting TSVs is a challenging computational problem. Sample heterogeneity (including differences between alleles in diploid organisms) is a critical confounding factor when identifying TSVs.

Avi Srivastava, Laraib Malik, Mohsen Zakeri, Hirak Sarkar, Charlotte Soneson, Michael I Love, Carl Kingsford, and Rob Patro (2019) Alignment and mapping methodology influence transcript abundance estimation. Genome Biology 21: 239..

The accuracy of transcript quantification using RNA-seq data depends on many factors, such as the choice of alignment or mapping method and the quantification model being adopted. While the choice of quantification model has been shown to be important, considerably less attention has been given to comparing the effect of various read alignment approaches on quantification accuracy. We investigate the effect of mapping and alignment on the accuracy of transcript quantification in both simulated and experimental data, as well as the effect on subsequent differential gene expression analysis.

Dan DeBlasio, Fiyinfoluwa Gbosibo, Carl Kingsford, and Guillaume Marcais (2019) Practical universal k-mer sets for minimizer schemes. To appear in ACM-BCB 2019.

Minimizer schemes have found widespread use in genomic applications as a way to quickly predict the matching probability of large sequences. Most methods for minimizer schemes use randomized (or close to randomized) ordering of k-mers when finding minimizers, but recent work has shown that not all non-lexicographic orderings perform the same.

Hongyi Xin, Mingfu Shao, and Carl Kingsford (2019) Context-Aware Seeds for Read Mapping. 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) 15:1--15:13 (2019) (journal version in Alg Mol Bio).

Most modern seed-and-extend NGS read mappers employ a seeding scheme that requires extracting t non-overlapping seeds in each read in order to find all valid mappings under an edit distance threshold of t. As t grows (such as in long reads with high error rate), this seeding scheme forces mappers to use more and shorter seeds, which increases the seed hits (seed frequencies) and therefore reduces the efficiency of mappers.

Laura H. Tung, Mingfu Shao, and Carl Kingsford (2019) Quantifying the Benefit Offered by Transcript Assembly on Single-Molecule Long Reads. Genome Biology *20*:287.

Third-generation sequencing technologies benefit transcriptome analysis by generating longer sequencing reads. However, not all single-molecule long reads represent full transcripts due to incomplete cDNA synthesis and the sequencing length limit of the platform. This drives a need for long read transcript assembly. We quantify the benefit that can be achieved by using a transcript assembler on long reads. Adding long-read-specific algorithms, we evolved Scallop to make Scallop-LR, a long-read transcript assembler, to handle the computational challenges arising from long read lengths and high error rates.

Quang Minh Hoàng, Nghia Hoang, Bryan Low, and Carl Kingsford (2019) Collective Model Fusion for Multiple Black-Box Experts. ICML PMLR 97:2742-2750, 2019.

Model fusion is a fundamental problem in collective machine learning (ML) where independent experts with heterogeneous learning architectures are required to combine expertise to improve predictive performance. This is particularly challenging in information-sensitive domains (e.g., medical records in health-care analytics) where experts do not have access to each other's internal architecture and local data.

Guillaume Marçais, Brad Solomon, Rob Patro, and Carl Kingsford (2019) Sketching and Sublinear Data Structures in Genomics. Annual Review of Biomedical Data Science *2*:93-118.

Large-scale genomics demands computational methods that scale sublinearly with the growth of data. We review several data structures and sketching techniques that have been used in genomic analysis methods. Specifically, we focus on four key ideas that take different approaches to achieve sublinear space usage and processing time: compressed full text indices, approximate membership query data structures, locality-sensitive hashing, and minimizers schemes. We describe these techniques at a high level and give several representative applications of each.

Preprint | Paper

View source

April 11, 2019 — Laura Tung, a Ph.D. student in the CPCB Computational Biology Program at Carnegie Mellon University has been awarded a NSF Graduate Research Fellowship. This highly competitive fellowship will partially fund her research for 3 years.

Congratulations!

View source

Vaibhav Rajan, Carl Kingsford, and Xiuwei Zhang (2019) Maximum Likelihood Reconstruction of Ancestral Networks by Integer Linear Programming. bioRxiv.

The evolutionary history of biological networks enables deep functional and evolutionary understanding of various bio-molecular processes. Network growth models, such as the Duplication-Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein-protein interactions (PPI) based on duplication and divergence. Current methods for model-based ancestral network reconstruction, primarily use greedy heuristics and yield sub-optimal solutions.

Dan DeBlasio, Kwanho Kim, and Carl Kingsford (2019) More accurate transcript assembly via parameter advising. The 2019 ICML Workshop on Computational Biology; journal version in Journal of Computational Biology.

Computational tools used for genomic analyses are becoming more accurate but also increasingly sophisticated and complex. This introduces a new problem in that these pieces of software have a large number of tunable parameters which often have a large influence on the results that are reported.

Guillaume Marçais, Dan DeBlasio, Prashant Pandey, and Carl Kingsford (2019) Locality sensitive hashing for the edit distance. Bioinformatics 35(14):i127-i135 (ISMB) 2019.

Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality-sensitive hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment.

Natalie Sauerwald, Yihang Shen, and Carl Kingsford (2019) Topological data analysis reveals principles of chromosome structure throughout cellular differentiation. 19th International Workshop on Algorithms in Bioinformatics (WABI 2019) 23:1--23:16 (2019).

Topological data analysis (TDA) is a mathematically well-founded set of methods to derive robust information about the structure and topology of data. It has been applied successfully in several biological contexts.