Algorithm to compute the longest run subsequence of a string
Project description
Longest Run Subsequence
Implementation of a solver for the Longest Run Subsequence Problem. Given a sequence as input, compute a longest subsequence such that there is at most one run for every character.
Example
A longest run subsequence of the string ccbcbbbdaaddd
is cccbbbaaddd
.
Algorithms
Depending on the properties of an instance the solver uses one of two algorithms to solve the problem. For long strings with small alphabets a dynamic programming approach is used, while short strings with large alphabets are solved via Integer Linear Programming. Every input instance is processed by reduction rules first to split it into smaller instances, if possible. Details can be found in [1]. Please consider citing this paper if you find the implementation useful for your work.
Installation
The Integer Linear Program algorithm is only available if PuLP is installed on the system. PuLP is a free API for modelling linear programs and available on PyPI or conda.
Usage
To solve Longest Run Subsequence instances, the function lrs
has to be
imported from the module.
Example code::
from longestrunsubsequence import lrs
print(lrs('ccbcbbbdaaddd'))
> [0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12]
The output is a list of indices, which represent the elements of the longest subsequence. The input can be a string or a list with arbitrary elements.
References
[1] Schrinner, S., Goel, M., Wulfert, M., Spohr, P., Schneeberger, K., Klau, G.W.: The Longest Run Subsequence Problem. In: Kingsford, C., Pisanti, N. (eds.) 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 172, pp. 6–1613. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). doi:10.4230/LIPIcs.WABI.2020.6. https://drops.dagstuhl.de/opus/volltexte/2020/12795
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file longestrunsubsequence-1.0.1.tar.gz
.
File metadata
- Download URL: longestrunsubsequence-1.0.1.tar.gz
- Upload date:
- Size: 9.6 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.3.0 pkginfo/1.5.0.1 requests/2.23.0 setuptools/52.0.0 requests-toolbelt/0.9.1 tqdm/4.46.0 CPython/3.8.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | c49134880da428425de2150569b6e6f7049509b6693cef920c32fca7ddf5e03f |
|
MD5 | 28edb02acd1fe22b97637cd044fbbee2 |
|
BLAKE2b-256 | eac1e5cdcb63d382f46073cba5be95c729721bfd42207a4d84fafac368788c7e |
File details
Details for the file longestrunsubsequence-1.0.1-py3-none-any.whl
.
File metadata
- Download URL: longestrunsubsequence-1.0.1-py3-none-any.whl
- Upload date:
- Size: 10.6 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.3.0 pkginfo/1.5.0.1 requests/2.23.0 setuptools/52.0.0 requests-toolbelt/0.9.1 tqdm/4.46.0 CPython/3.8.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 202da0be7e5d862589f249edb48191e9f27193c05041170d3838f160e5063412 |
|
MD5 | 5913ad27f481704641d351e190237a84 |
|
BLAKE2b-256 | 420dedf67a8ec260ce1181f2ccbd677b82f9c2da7014ffd68effaf60094cb8b8 |