Collaborative Research: NSF-BSF: CIF: Small: An Information Theory for Out-of-Order Data: Applications in Genomics, Molecular Storage, and Beyond

Most of the digital technology around us processes and stores information in a sequential, well-ordered manner. For example, a computer hard drive stores data bits in a structured way that allows them to be retrieved in order. Cell phone systems transmit and receive data as sequences of bits coded to allow the receiver to reconstruct the information in the same order it was sent. Recent technological advances such as DNA sequencing technologies, however, defy this ordered information paradigm. Such technologies generate data consisting of many short, out-of-order fragments. Processing this data is akin to assembling a jigsaw puzzle, where the desired information is only conveyed by the final assembled picture. Developing powerful algorithms for these tasks is important for several applications in the field of genomics and for the development of emerging molecular data storage technologies. The goal of this project is to extend techniques from the ordered digital world - codes, algorithms, and an information-theoretic framework - to these emerging out-of-order settings. This should enable new data storage paradigms to be deployed and lead to the development of new computational methods to analyze genomics data. The project will seek to extend Information Theory techniques to out-of-order information scenarios and to characterize how much information can be reliably conveyed by an unordered set of data fragments. The research will be organized along three thrusts with important practical applications. Motivated by tasks in immunogenomics and resistomics, the first thrust will focus on the problem of recovering a set of similar-looking sequences (genes, in most applications) from a set of unordered fragments (the DNA sequencing reads). This will lead to new algorithms to characterize the presence of antimicrobial resistance genes in a microbial community. The second thrust will address the problem of reordering a set of unordered fragments given a noisy reference. This has applications in reference-based genome assembly (when the genome of a related species is available) and in the problem of aligning out-of-order data across two databases. Motivated by molecular data storage and its potential for addressing ever-increasing data storage demands, the third thrust will focus on fundamental limits and coding strategies for out-of-order channels. This includes the development of near-capacity-achieving codes for molecular storage, the analysis of the combined effects of fragmentation and symbol-level noise, and the design of efficient codes that minimize synthesis costs. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.