Collapse a set of redundant kmers to use IUPAC degenerate bases

Related tags

Miscellaneousencodingbioinformaticskmeriupac
Overview

kmer-collapse

Collapse a set of redundant kmers to use IUPAC degenerate bases

Overview

Given an input set of kmers, find the smallest set of kmers that encapsulates all diversity in the input set using IUPAC degenerate bases. This aims to solve the problem described here: https://www.biostars.org/p/9498272/

Usage

Install the marisa-trie library, if necessary.

Modify the script's input variable to specify desired sequences, and then run the script:

$ python kmer-collapse.py
{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "ACAAAAAAAA",
        "AGAAAAAAAA"
    ],
    "encoded_output": [
        "WAAAAAAAAA",
        "ASAAAAAAAA"
    ]
}

Notes

This has not been tested with any kmer sets but those examples provided. However, it aims to be scalable by pruning combinations of sub-kmers along the way, which would otherwise yield incorrect encodings. This also uses a trie for faster prefix testing. If futher performance is needed, some easy wins would be to cache sub-kmer tests, since most of these test outcomes would be redundant.

Additionally, no error checking is done on the input kmer alphabet or on the consistency of kmer lengths. It may be useful to validate input before using this script.

Examples

These examples are available from the script by uncommenting the relevant input.

A

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA"
    ],
    "encoded_output": [
        "WAAAAAAAAA"
    ]
}

B

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "GCGAAAAAAA"
    ],
    "encoded_output": [
        "GCGAAAAAAA",
        "WAAAAAAAAA"
    ]
}

C

{
    "input": [
        "AAAAAAAAAA"
    ],
    "encoded_output": [
        "AAAAAAAAAA"
    ]
}

D

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "CAAAAAAAAA",
        "GAAAAAAAAA"
    ],
    "encoded_output": [
        "NAAAAAAAAA"
    ]
}

E

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "TTAAAAAAAA",
        "ATAAAAAAAA"
    ],
    "encoded_output": [
        "WWAAAAAAAA"
    ]
}

F

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "CAAAAAAAAA",
        "GAAAAAAAAA",
        "TACAGATACA",
        "AACAGAAAAA"
    ],
    "encoded_output": [
        "NAAAAAAAAA",
        "TACAGATACA",
        "AACAGAAAAA"
    ]
}

G

{
    "input": [
        "AAAAAAAAAA",
        "TAAAAAAAAA",
        "ACAAAAAAAA",
        "AGAAAAAAAA"
    ],
    "encoded_output": [
        "ASAAAAAAAA",
        "WAAAAAAAAA"
    ]
}
Owner
Alex Reynolds
Pug caregiver, curler, cyclist, gardener, beginning French scholar
Alex Reynolds
GitHub Repository
Expression interpreter written in Python

Calc Interpreter An interpreter modeled after a calculator implemented in Python 3. The program currently only supports basic mathematical expressions

1 Oct 17, 2021
A free micro-blog written in Python and powered by Heroku. *Merge requests are appreciated!*

Background Hobo is an ultra-lightweight blog engine written in Python. It has two dependencies, fully integrated into the codebase with no additional

Andrew Nelder 48 Jan 28, 2021
Get a link to the web version of a git-tracked file or directory

githyperlink Get a link to the web version of a git-tracked file or directory. Applies to GitHub and GitLab remotes (and maybe others but those are no

Tomas Fiers 2 Nov 08, 2022
External Network Pentest Automation using Shodan API and other tools.

Chopin External Network Pentest Automation using Shodan API and other tools. Workflow Input a file containing CIDR ranges. Converts CIDR ranges to ind

Aditya Dixit 9 Aug 04, 2022
Hacking and Learning consistently for 100 days straight af.

#100DaysOfHacking Hacking and Learning consistently for 100 days straight af. [yes, no breaks except mental-break ones, Obviously.] This Repo is one s

FENIL SHAH 17 Sep 09, 2022
python3 scrip for case conversion of source code files writen in fixed form fortran

convert_FORTRAN_case python3 scrip for case conversion of source code files writen in fixed form fortran python3 scrip for case conversion of source c

7 Sep 20, 2022
A python library for writing parser-based interactive fiction.

About IntFicPy A python library for writing parser-based interactive fiction. Currently in early development. IntFicPy Docs Parser-based interactive f

Rita Lester 31 Nov 23, 2022
In this repo i inherit the pos module and added QR code to pos receipt

odoo-pos-inherit In this repo i inherit the pos module and added QR code to pos receipt 1- Create new Odoo Module using command line $ python odoo-bin

5 Apr 09, 2022
VirtualBox Power Driver for MAAS (Metal as a Service)

vboxpower VirtualBox Power Driver for MAAS (Metal as a Service) A way to manage the power of VirtualBox virtual machines via the MAAS webhook driver.

Saeid Bostandoust 131 Dec 17, 2022
Very simple encoding scheme that will encode data as a series of OwOs or UwUs.

OwO Encoder Very simple encoding scheme that will encode data as a series of OwOs or UwUs. The encoder is a simple state machine. Still needs a decode

1 Nov 15, 2021
Standalone PyQGIS application for executing custom scripts without a QGIS GUI.

PyQGIS Standalone Script Executer Standalone PyQGIS application that is able to run a custom script, in this case Proximity.py without the need of a G

6 Sep 23, 2022
Back-end API for the reternal framework

RE:TERNAL RE:TERNAL is a centralised purple team simulation platform. Reternal uses agents installed on a simulation network to execute various known

Joey Dreijer 7 Apr 15, 2022
CountdownTimer - Countdown Timer For Python

Countdown Timer This python script asks for the user time (input) in seconds, an

Arinzechukwu Okoye 1 Jan 01, 2022
A python script to run any executable and pass test cases to it's stdin and compare stdout with correct output.

quera_testcase_checker A python script to run any executable and pass test cases to it's stdin and compare stdout with correct output. proper way to u

k3y1 1 Nov 15, 2021
A Tool to validate domestic New Zealand vaccine passes

Vaccine Validator Tool to validate domestic New Zealand vaccine passes Create a new virtual environment: python3 -m venv ./venv Activate virtual envi

8 May 01, 2022
How to create the game Rock, Paper, Scissors in Python

Rock, Paper, Scissors! If you want to learn how to do interactive games using Python, then this is great start for you. In this code, You will learn h

SplendidSpidey 1 Dec 18, 2021
Telegram bot to search quotes from brainyquote.com

Brainy Quote Bot @BrainQuoteBot A star ⭐ from you means a lot to us! Telegram bot to search quotes from brainyquote.com Usage Deploy to Heroku Tap on

21 Nov 24, 2022
A module comment generator for python

Module Comment Generator The comment style is as a tribute to the comment from the RA . The comment generator can parse the ast tree from the python s

飘尘 1 Oct 21, 2021
Adds a Bake node to Blender's shader node system

Bake to Target This Blender Addon adds a new shader node type capable of reducing the texture-bake step to a single button press. Please note that thi

Thomas 8 Oct 04, 2022
DD监控室第一版

DD监控室 运行指南

执明神君 1.2k Dec 31, 2022