Cargando…

Linearization of genome sequence graphs revisited

The need to include the genetic variation within a population into a reference genome led to the concept of a genome sequence graph. Nodes of such a graph are labeled with DNA sequences occurring in represented genomes. Due to double-stranded nature of DNA, each node may be oriented in one of two po...

Descripción completa

Detalles Bibliográficos
Autores principales: Lisiecka, Anna, Dojer, Norbert
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Elsevier 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8264155/
https://www.ncbi.nlm.nih.gov/pubmed/34278263
http://dx.doi.org/10.1016/j.isci.2021.102755
_version_ 1783719489606516736
author Lisiecka, Anna
Dojer, Norbert
author_facet Lisiecka, Anna
Dojer, Norbert
author_sort Lisiecka, Anna
collection PubMed
description The need to include the genetic variation within a population into a reference genome led to the concept of a genome sequence graph. Nodes of such a graph are labeled with DNA sequences occurring in represented genomes. Due to double-stranded nature of DNA, each node may be oriented in one of two possible ways, resulting in marking one end of the labeling sequence as in-side and the other as out-side. Edges join pairs of sides and reflect adjacency between node sequences in genomes constituting the graph. Linearization of a sequence graph aims at orienting and ordering graph nodes in a way that makes it more efficient for visualization and further analysis, e.g. access and traversal. We propose a new linearization algorithm, called ALIBI – Algorithm for Linearization by Incremental graph BuIlding. The evaluation shows that ALIBI is computationally very efficient and generates high-quality results.
format Online
Article
Text
id pubmed-8264155
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Elsevier
record_format MEDLINE/PubMed
spelling pubmed-82641552021-07-16 Linearization of genome sequence graphs revisited Lisiecka, Anna Dojer, Norbert iScience Article The need to include the genetic variation within a population into a reference genome led to the concept of a genome sequence graph. Nodes of such a graph are labeled with DNA sequences occurring in represented genomes. Due to double-stranded nature of DNA, each node may be oriented in one of two possible ways, resulting in marking one end of the labeling sequence as in-side and the other as out-side. Edges join pairs of sides and reflect adjacency between node sequences in genomes constituting the graph. Linearization of a sequence graph aims at orienting and ordering graph nodes in a way that makes it more efficient for visualization and further analysis, e.g. access and traversal. We propose a new linearization algorithm, called ALIBI – Algorithm for Linearization by Incremental graph BuIlding. The evaluation shows that ALIBI is computationally very efficient and generates high-quality results. Elsevier 2021-06-19 /pmc/articles/PMC8264155/ /pubmed/34278263 http://dx.doi.org/10.1016/j.isci.2021.102755 Text en © 2021 The Authors https://creativecommons.org/licenses/by/4.0/This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Lisiecka, Anna
Dojer, Norbert
Linearization of genome sequence graphs revisited
title Linearization of genome sequence graphs revisited
title_full Linearization of genome sequence graphs revisited
title_fullStr Linearization of genome sequence graphs revisited
title_full_unstemmed Linearization of genome sequence graphs revisited
title_short Linearization of genome sequence graphs revisited
title_sort linearization of genome sequence graphs revisited
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8264155/
https://www.ncbi.nlm.nih.gov/pubmed/34278263
http://dx.doi.org/10.1016/j.isci.2021.102755
work_keys_str_mv AT lisieckaanna linearizationofgenomesequencegraphsrevisited
AT dojernorbert linearizationofgenomesequencegraphsrevisited