1 Search Results for "Polevikov, Evgeny"

Synteny Paths for Assembly Graphs Comparison

Authors: Evgeny Polevikov and Mikhail Kolmogorov

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

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.

Cite as

Evgeny Polevikov and Mikhail Kolmogorov. Synteny Paths for Assembly Graphs Comparison. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

  author =	{Polevikov, Evgeny and Kolmogorov, Mikhail},
  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 =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.24},
  URN =		{urn:nbn:de:0030-drops-110545},
  doi =		{10.4230/LIPIcs.WABI.2019.24},
  annote =	{Keywords: Assembly graphs, Genome assembly, Synteny blocks, Comparative Genomics}
  • Refine by Author
  • 1 Kolmogorov, Mikhail
  • 1 Polevikov, Evgeny

  • Refine by Classification
  • 1 Applied computing → Bioinformatics

  • Refine by Keyword
  • 1 Assembly graphs
  • 1 Comparative Genomics
  • 1 Genome assembly
  • 1 Synteny blocks

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019