License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2019.24
URN: urn:nbn:de:0030-drops-110545
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11054/
Go to the corresponding LIPIcs Volume Portal

Polevikov, Evgeny ; Kolmogorov, Mikhail

Synteny Paths for Assembly Graphs Comparison

pdf-format:
LIPIcs-WABI-2019-24.pdf (0.7 MB)

Abstract

Despite the recent developments of long-read sequencing technologies, it is still difficult to produce complete assemblies of eukaryotic genomes in an automated fashion. Genome assembly software typically output assembled fragments (contigs) along with assembly graphs, that encode all possible layouts of these contigs. Graph representation of the assembled genome can be useful for gene discovery, haplotyping, structural variations analysis and other applications. To facilitate the development of new graph-based approaches, it is important to develop algorithms for comparison and evaluation of assembly graphs produced by different software. In this work, we introduce synteny paths: maximal paths of homologous sequence between the compared assembly graphs. We describe Asgan - an algorithm for efficient synteny paths decomposition, and use it to evaluate assembly graphs of various bacterial assemblies produced by different approaches. We then apply Asgan to discover structural variations between the assemblies of 15 Drosophila genomes, and show that synteny paths are robust to contig fragmentation. The Asgan tool is freely available at: https://github.com/epolevikov/Asgan.

BibTeX - Entry

@InProceedings{polevikov_et_al:LIPIcs:2019:11054,
  author =	{Evgeny Polevikov and Mikhail Kolmogorov},
  title =	{{Synteny Paths for Assembly Graphs Comparison}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Katharina T. Huber and Dan Gusfield},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11054},
  URN =		{urn:nbn:de:0030-drops-110545},
  doi =		{10.4230/LIPIcs.WABI.2019.24},
  annote =	{Keywords: Assembly graphs, Genome assembly, Synteny blocks, Comparative Genomics}
}

Keywords: Assembly graphs, Genome assembly, Synteny blocks, Comparative Genomics
Collection: 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Issue Date: 2019
Date of publication: 03.09.2019
Supplementary Material: The Asgan tool is freely available at: https://github.com/epolevikov/Asgan.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI