DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2020.6

The Longest Run Subsequence Problem

Authors: Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract

Genome assembly is one of the most important problems in computational genomics. Here, we suggest addressing the scaffolding phase, in which contigs need to be linked and ordered to obtain larger pseudo-chromosomes, by means of a second incomplete assembly of a related species. The idea is to use alignments of binned regions in one contig to find the most homologous contig in the other assembly. We show that ordering the contigs of the other assembly can be expressed by a new string problem, the longest run subsequence problem (LRS). We show that LRS is NP-hard and present reduction rules and two algorithmic approaches that, together, are able to solve large instances of LRS to provable optimality. In particular, they can solve realistic instances resulting from partial Arabidopsis thaliana assemblies in short computation time. Our source code and all data used in the experiments are freely available.

Cite as

Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau. The Longest Run Subsequence Problem. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schrinner_et_al:LIPIcs.WABI.2020.6,
  author =	{Schrinner, Sven and Goel, Manish and Wulfert, Michael and Spohr, Philipp and Schneeberger, Korbinian and Klau, Gunnar W.},
  title =	{{The Longest Run Subsequence Problem}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.6},
  URN =		{urn:nbn:de:0030-drops-127951},
  doi =		{10.4230/LIPIcs.WABI.2020.6},
  annote =	{Keywords: alignments, assembly, string algorithm, longest subsequence}
}

Search Results

Documents authored by Wulfert, Michael

The Longest Run Subsequence Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message