Grant: Discovery Grants Program - Individual
Dalhousie University
$34,000.00
Compact Data Structures for Computational Genomics
FY 2022-23
Summary
The largest genomic databases now occupy hundreds of terabytes uncompressed. They are an invaluable resource for researchers and physicians but a challenge for computer scientists because standard tools become impractical at such scales. We can compress these databases extremely well because they are repetitive, but we must still modify our tools to work with their compressed representations. For example, mapping assembly is a basic task in bioinformatics: indexing a reference genome we have already assembled and then, for each read of a new genome, quickly finding the substrings of the reference it matches most closely. Even when a genome is 99.9% the same as the reference, though, genomes are so big that the 0.1% difference is enough to cause many thousands of reads to remain unmapped. It helps significantly to index a "pan-genome" reference representing many genomes but popular tools for read-mapping cannot handle databases containing more than a few genomes, because they do not take advantage of the genomes' similarity. We recently devised a tool called the r-index that can index hundreds or thousands of human genomes using reasonable memory space. We have released a basic practical implementation, which will serve as a starting point for this project. Adding new functionalities to the r-index is more difficult than adding them to current read-mappers, however, because now we need to compress even small auxiliary data structures. First, we will extend the r-index to find maximal exact matches and combine it with recent software that stores a pan-genome as a variation graph. At the moment that software tries to index a graph but it can just as well index a genomic database and store a mapping from each genome to a path in the graph. This way, given a read, we first map it to matching substrings in the genomes and then map those to paths in the variation graph. Second, we will extend the r-index such that, when there are many matches for a read in our genomic database that all map to the same path in the graph, it will return only summary statistics instead of reporting them individually. Such queries are essentially document listing and document counting over highly repetitive collections, something I have previously studied. Third, we will investigate further Wheeler graphs, a framework for data structures based on the Burrows-Wheeler Transform. Such data structures include the FM-index underlying popular read-mappers; some compact representations of de Bruijn graphs; and variation-graph indexes. Our framework has already inspired a method for further compressing the r-index and for compressed indexing of readsets. We will work to integrate practical implementations of an extended r-index into commercial and research sequencing pipelines. I am confident this project will help computer scientists meet some of the challenges posed by the flood of genomic data, and thus help biologists and physicians realize its potential.
Program
Discovery Grants Program - Individual
Recipient
Location
Nova Scotia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2020-07185
Name nom
Gagie, Travis
Department département
Computer Science, Faculty of - Computer Science, Faculty of
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2020
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:3
Partie
1
Nb partie
5
Application title
Compact Data Structures for Computational Genomics
Application summary
The largest genomic databases now occupy hundreds of terabytes uncompressed. They are an invaluable resource for researchers and physicians but a challenge for computer scientists because standard tools become impractical at such scales. We can compress these databases extremely well because they are repetitive, but we must still modify our tools to work with their compressed representations. For example, mapping assembly is a basic task in bioinformatics: indexing a reference genome we have already assembled and then, for each read of a new genome, quickly finding the substrings of the reference it matches most closely. Even when a genome is 99.9% the same as the reference, though, genomes are so big that the 0.1% difference is enough to cause many thousands of reads to remain unmapped. It helps significantly to index a "pan-genome" reference representing many genomes but popular tools for read-mapping cannot handle databases containing more than a few genomes, because they do not take advantage of the genomes' similarity. We recently devised a tool called the r-index that can index hundreds or thousands of human genomes using reasonable memory space. We have released a basic practical implementation, which will serve as a starting point for this project. Adding new functionalities to the r-index is more difficult than adding them to current read-mappers, however, because now we need to compress even small auxiliary data structures. First, we will extend the r-index to find maximal exact matches and combine it with recent software that stores a pan-genome as a variation graph. At the moment that software tries to index a graph but it can just as well index a genomic database and store a mapping from each genome to a path in the graph. This way, given a read, we first map it to matching substrings in the genomes and then map those to paths in the variation graph. Second, we will extend the r-index such that, when there are many matches for a read in our genomic database that all map to the same path in the graph, it will return only summary statistics instead of reporting them individually. Such queries are essentially document listing and document counting over highly repetitive collections, something I have previously studied. Third, we will investigate further Wheeler graphs, a framework for data structures based on the Burrows-Wheeler Transform. Such data structures include the FM-index underlying popular read-mappers; some compact representations of de Bruijn graphs; and variation-graph indexes. Our framework has already inspired a method for further compressing the r-index and for compressed indexing of readsets. We will work to integrate practical implementations of an extended r-index into commercial and research sequencing pipelines. I am confident this project will help computer scientists meet some of the challenges posed by the flood of genomic data, and thus help biologists and physicians realize its potential.