The Library
RecGraph: recombination-aware alignment of sequences to variation graphs
Tools
Avila Cartes, Jorge, Bonizzoni, Paola, Ciccolella, Simone, Della Vedova, Gianluca, Denti, Luca, Didelot, Xavier, Monti, Davide, Pirola, Yuri and Valencia, Alfonso (2024) RecGraph: recombination-aware alignment of sequences to variation graphs. Bioinformatics . doi:10.1093/bioinformatics/btae292 ISSN 1367-4803. (In Press)
|
PDF
btae292.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (545Kb) | Preview |
Official URL: http://doi.org/10.1093/bioinformatics/btae292
Abstract
Motivation
Bacterial genomes present more variability than human genomes, which requires important adjustments in computational tools that are developed for human data. In particular, bacteria exhibit a mosaic structure due to homologous recombinations, but this fact is not sufficiently captured by standard read mappers that align against linear reference genomes. The recent introduction of pangenomics provides some insights in that context, as a pangenome graph can represent the variability within a species. However, the concept of sequence-to-graph alignment that captures the presence of recombinations has not been previously investigated.
Results
In this paper, we present the extension of the notion of sequence-to-graph alignment to a variation graph that incorporates a recombination, so that the latter are explicitly represented and evaluated in an alignment. Moreover, we present a dynamic programming approach for the special case where there is at most a recombination–we implement this case as RecGraph. From a modeling point of view, a recombination corresponds to identifying a new path of the variation graph, where the new arc is composed of two halves, each extracted from an original path, possibly joined by a new arc. Our experiments show that RecGraph accurately aligns simulated recombinant bacterial sequences that have at most a recombination, providing evidence for the presence of recombination events.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QH Natural history Q Science > QR Microbiology |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Life Sciences (2010- ) | ||||||||||||
Library of Congress Subject Headings (LCSH): | Bacterial genomes , Bacterial genomes -- Data processing, Genomics -- Technique -- Computer programs, Bacterial genetics , Sequence alignment (Bioinformatics) , Dynamic programming , Computational biology | ||||||||||||
Journal or Publication Title: | Bioinformatics | ||||||||||||
Publisher: | Oxford University Press | ||||||||||||
ISSN: | 1367-4803 | ||||||||||||
Official Date: | 2024 | ||||||||||||
Dates: |
|
||||||||||||
DOI: | 10.1093/bioinformatics/btae292 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | In Press | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 2 May 2024 | ||||||||||||
Date of first compliant Open Access: | 3 May 2024 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year