XHap: haplotype assembly using long-distance read correlations learned by transformers.

Summary: Reconstructing haplotypes of an organism from a set of sequencing reads is a computationally challenging (NP-hard) problem. In reference-guided settings, at the core of haplotype assembly is the task of clustering reads according to their origin, i.e.

Graph-Based Reconstruction and Analysis of Disease Transmission Networks Using Viral Genomic Data.

Understanding the patterns of viral disease transmissions helps establish public health policies and aids in controlling and ending a disease outbreak. Classical methods for studying disease transmission dynamics that rely on epidemiological data, such as times of sample collection and duration of exposure intervals, struggle to provide desired insight due to limited informativeness of such data. A more precise characterization of disease transmissions may be acquired from sequencing data that reveal genetic distance between viral genomes in patient samples.

ComHapDet: a spatial community detection algorithm for haplotype assembly.

Background: Haplotypes, the ordered lists of single nucleotide variations that distinguish chromosomal sequences from their homologous pairs, may reveal an individual's susceptibility to hereditary and complex diseases and affect how our bodies respond to therapeutic drugs. Reconstructing haplotypes of an individual from short sequencing reads is an NP-hard problem that becomes even more challenging in the case of polyploids. While increasing lengths of sequencing reads and insert sizes helps improve accuracy of reconstruction, it also exacerbates computational complexity of the haplotype assembly task.

Multiplexed identification, quantification and genotyping of infectious agents using a semiconductor biochip.

The emergence of pathogens resistant to existing antimicrobial drugs is a growing worldwide health crisis that threatens a return to the pre-antibiotic era. To decrease the overuse of antibiotics, molecular diagnostics systems are needed that can rapidly identify pathogens in a clinical sample and determine the presence of mutations that confer drug resistance at the point of care. We developed a fully integrated, miniaturized semiconductor biochip and closed-tube detection chemistry that performs multiplex nucleic acid amplification and sequence analysis.

Viral quasispecies reconstruction via tensor factorization with successive read removal.

Motivation: As RNA viruses mutate and adapt to environmental changes, often developing resistance to anti-viral vaccines and drugs, they form an ensemble of viral strains--a viral quasispecies. While high-throughput sequencing (HTS) has enabled in-depth studies of viral quasispecies, sequencing errors and limited read lengths render the problem of reconstructing the strains and estimating their spectrum challenging. Inference of viral quasispecies is difficult due to generally non-uniform frequencies of the strains, and is further exacerbated when the genetic distances between the strains are small.

Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids.

Background: Haplotype assembly is the task of reconstructing haplotypes of an individual from a mixture of sequenced chromosome fragments. Haplotype information enables studies of the effects of genetic variations on an organism's phenotype. Most of the mathematical formulations of haplotype assembly are known to be NP-hard and haplotype assembly becomes even more challenging as the sequencing technology advances and the length of the paired-end reads and inserts increases.

aBayesQR: A Bayesian Method for Reconstruction of Viral Populations Characterized by Low Diversity.

RNA viruses replicate with high mutation rates, creating closely related viral populations. The heterogeneous virus populations, referred to as viral quasispecies, rapidly adapt to environmental changes thus adversely affecting efficiency of antiviral drugs and vaccines. Therefore, studying the underlying genetic heterogeneity of viral populations plays a significant role in the development of effective therapeutic treatments.

QSdpR: Viral quasispecies reconstruction via correlation clustering.

RNA viruses are characterized by high mutation rates that give rise to populations of closely related genomes, known as viral quasispecies. Underlying heterogeneity enables the quasispecies to adapt to changing conditions and proliferate over the course of an infection. Determining genetic diversity of a virus (i.

End-to-End Optimization of High-Throughput DNA Sequencing.

At the core of Illumina's high-throughput DNA sequencing platforms lies a biophysical surface process that results in a random geometry of clusters of homogeneous short DNA fragments typically hundreds of base pairs long-bridge amplification. The statistical properties of this random process and the lengths of the fragments are critical as they affect the information that can be subsequently extracted, that is, density of successfully inferred DNA fragment reads. The ensembles of overlapping DNA fragment reads are then used to computationally reconstruct the much longer target genome sequence.

Decoding Genetic Variations: Communications-Inspired Haplotype Assembly.

High-throughput DNA sequencing technologies allow fast and affordable sequencing of individual genomes and thus enable unprecedented studies of genetic variations. Information about variations in the genome of an individual is provided by haplotypes, ordered collections of single nucleotide polymorphisms. Knowledge of haplotypes is instrumental in finding genes associated with diseases, drug development, and evolutionary studies.

Semi-Supervised Affinity Propagation with Soft Instance-Level Constraints.

Soft-constraint semi-supervised affinity propagation (SCSSAP) adds supervision to the affinity propagation (AP) clustering algorithm without strictly enforcing instance-level constraints. Constraint violations lead to an adjustment of the AP similarity matrix at every iteration of the proposed algorithm and to addition of a penalty to the objective function. This formulation is particularly advantageous in the presence of noisy labels or noisy constraints since the penalty parameter of SCSSAP can be tuned to express our confidence in instance-level constraints.

Joint haplotype assembly and genotype calling via sequential Monte Carlo algorithm.

Background: Genetic variations predispose individuals to hereditary diseases, play important role in the development of complex diseases, and impact drug metabolism. The full information about the DNA variations in the genome of an individual is given by haplotypes, the ordered lists of single nucleotide polymorphisms (SNPs) located on chromosomes. Affordable high-throughput DNA sequencing technologies enable routine acquisition of data needed for the assembly of single individual haplotypes.

Designing optimal mortality risk prediction scores that preserve clinical knowledge.

Many in-hospital mortality risk prediction scores dichotomize predictive variables to simplify the score calculation. However, hard thresholding in these additive stepwise scores of the form "add x points if variable v is above/below threshold t" may lead to critical failures. In this paper, we seek to develop risk prediction scores that preserve clinical knowledge embedded in features and structure of the existing additive stepwise scores while addressing limitations caused by variable dichotomization.

SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming.

Background: The goal of haplotype assembly is to infer haplotypes of an individual from a mixture of sequenced chromosome fragments. Limited lengths of paired-end sequencing reads and inserts render haplotype assembly computationally challenging; in fact, most of the problem formulations are known to be NP-hard. Dimensions (and, therefore, difficulty) of the haplotype assembly problems keep increasing as the sequencing technology advances and the length of reads and inserts grow.

Bayesian active learning for drug combinations.

The dynamics of complex diseases are governed by intricate interactions of myriad factors. Drug combinations, formed by mixing several single-drug treatments at various doses, can enhance the effectiveness of the therapy by targeting multiple contributing factors. The main challenge in designing drug combinations is the highly nonlinear interaction of the constituent drugs.

Base calling for high-throughput short-read sequencing: dynamic programming solutions.

Background: Next-generation DNA sequencing platforms are capable of generating millions of reads in a matter of days at rapidly reducing costs. Despite its proliferation and technological improvements, the performance of next-generation sequencing remains adversely affected by the imperfections in the underlying biochemical and signal acquisition procedures. To this end, various techniques, including statistical methods, are used to improve read lengths and accuracy of these systems.

ParticleCall: a particle filter for base calling in next-generation sequencing systems.

Background: Next-generation sequencing systems are capable of rapid and cost-effective DNA sequencing, thus enabling routine sequencing tasks and taking us one step closer to personalized medicine. Accuracy and lengths of their reads, however, are yet to surpass those provided by the conventional Sanger sequencing method. This motivates the search for computationally efficient algorithms capable of reliable and accurate detection of the order of nucleotides in short DNA fragments from the acquired data.

OnlineCall: fast online parameter estimation and base calling for illumina's next-generation sequencing.

Motivation: Next-generation DNA sequencing platforms are becoming increasingly cost-effective and capable of providing enormous number of reads in a relatively short time. However, their accuracy and read lengths are still lagging behind those of conventional Sanger sequencing method. Performance of next-generation sequencing platforms is fundamentally limited by various imperfections in the sequencing-by-synthesis and signal acquisition processes.

A dual Kalman filter for parameter-state estimation in real-time DNA microarrays.

Affinity-based biosensors rely on chemical attraction between analytes (targets) and their molecular complements (probes) to detect presence and quantify amounts of the analytes of interest. Real-time DNA microarrays acquire multiple temporal samples of the target-probe binding process. In this paper, estimation of the amount of targets based on early kinetics of the binding reaction is studied.

FRET-based real-time DNA microarrays.

We present a quantification method for affinity-based DNA microarrays which is based on the real-time measurements of hybridization kinetics. This method, i.e.

Real-time DNA microarray analysis.

We present a quantification method for affinity-based DNA microarrays which is based on the real-time measurements of hybridization kinetics. This method, i.e.