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.2020.6
URN: urn:nbn:de:0030-drops-127951
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12795/
Go to the corresponding LIPIcs Volume Portal

Schrinner, Sven ; Goel, Manish ; Wulfert, Michael ; Spohr, Philipp ; Schneeberger, Korbinian ; Klau, Gunnar W.

The Longest Run Subsequence Problem

pdf-format:
LIPIcs-WABI-2020-6.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{schrinner_et_al:LIPIcs:2020:12795,
  author =	{Sven Schrinner and Manish Goel and Michael Wulfert and Philipp Spohr and Korbinian Schneeberger and Gunnar W. Klau},
  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 =	{Carl Kingsford and Nadia Pisanti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12795},
  URN =		{urn:nbn:de:0030-drops-127951},
  doi =		{10.4230/LIPIcs.WABI.2020.6},
  annote =	{Keywords: alignments, assembly, string algorithm, longest subsequence}
}

Keywords: alignments, assembly, string algorithm, longest subsequence
Collection: 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)
Issue Date: 2020
Date of publication: 25.08.2020
Supplementary Material: Source code and all data used in the experiments available at https://github.com/AlBi-HHU/longest-run-subsequence.

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