Data

Tools

Indexes

Applications

Experiments

Open Source Science

lcus_naive

LCuS.py is a naive O(n^5) approach to solving the longest cubic subsequence (LCuS) problem. For a string of characters, LCuS.py identifies the longest subsequence repeated three distinct times. It finds the optimal breakpoints to seperate the string into three consecutive substrings, each containing an interation of the subsequence.

https://github.com/robynburger/lcus_naive

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (8.6%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

LCuS.py is a naive O(n^5) approach to solving the longest cubic subsequence (LCuS) problem. For a string of characters, LCuS.py identifies the longest subsequence repeated three distinct times. It finds the optimal breakpoints to seperate the string into three consecutive substrings, each containing an interation of the subsequence.

Basic Info
  • Host: GitHub
  • Owner: robynburger
  • Language: Python
  • Default Branch: main
  • Homepage:
  • Size: 79.1 KB
Statistics
  • Stars: 0
  • Watchers: 3
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created almost 2 years ago · Last pushed over 1 year ago
Metadata Files
Readme Citation

README.md

Description of LCuS

LCuS.py is a naive O(n^5) approach to solving the longest cubic subsequence (LCuS) problem.

For a string of characters, LCuS.py identifies the longest subsequence repeated three distinct times. It finds the optimal breakpoints to seperate the string into three consecutive substrings, each containing an interation of the subsequence. It then returns these indices and three matrices, F, D, and E. For given (valid) values of j, l, m, for all i in the range (1,...,j-1) and all k in the range (j,...,l-1):

  • the F matrix holds values all f(i, k)
  • the D matrix holds values all d(i, k)
  • the E matrix holds values all e(i, k)

For more information, see paper (* citation)

Requirements

  1. Install python 3.12 or higher
  2. Use Conda or other similar environment to run NumPy package: (https://www.numpy.org)

Running LCuS

Clone the repository: $ git clone https://github.com/robynburger/LCS_naieve

Run LCuS.py: $ python LCuS.py

Enter command line arguments: ``` Enter string:

Use ideal parameters? (Yes/No): If user types 'Yes: Your file was saved: results/s/ideal.txt If user types 'No': Enter positive integers j, l, m:

Note: 1 <= i < j <= k < l <= m <= {len(s)}.

j:

l:

m:

Your file was saved: results/s/jlm.txt ```

Authors and Acknowledgements

Written by Robyn Burger and Allison Shi under the mentorship of Dr. Brendan Mumey and Dr. Adiesha Liyanage.

Funded by the National Science Foundation (NSF) as part of research conducted at Montana State University for the summer 2024 Algorithms REU.

Adapated from longest tandem subsequence problem:

Kosowski, Adrian., An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem, Lecture Notes in Computer Science, volume 3246 (2004) 93-100.

Owner

  • Login: robynburger
  • Kind: user

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Burger"
  given-names: "Robyn"
- family-names: "Shi"
  given-names: "Allison"
title: "Longest Cubic Subsequence Problem"
version: 2.0.4
url: "https://github.com/robynburger/LCS_Naive"

GitHub Events

Total
Last Year