A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem

Authors

  • Sebastian Deorowicz Institute of Informatics, Silesian University of Technology, Gliwice

Keywords:

Longest increasing subsequence, sliding window, pattern matching

Abstract

A longest increasing subsequence problem (LIS) is a well-known combinatorial problem with applications mainly in bioinformatics, where it is used in various projects on DNA sequences. Recently, a number of generalisations of this problem were proposed. One of them is to find an LIS among all fixed-size windows of the input sequence (LISW). We propose an algorithm for the LISW problem based on cover representation of the sequence that outperforms the existing methods for some class of the input sequences.

Downloads

Download data is not yet available.

Downloads

Published

2013-01-24

How to Cite

Deorowicz, S. (2013). A Cover-Merging-Based Algorithm for the Longest Increasing Subsequence in a Sliding Window Problem. COMPUTING AND INFORMATICS, 31(6), 1217–1233. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/1305

Issue

Vol. 31 No. 6 (2012): Computing and Informatics

Section

Articles