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...
Autores principales: | , |
---|---|
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 |