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
Vaksina - Vaksina COVID QR Validation Checker With Python

Vaksina COVID QR Validation Checker Vaksina is a general purpose library intende

Michael Casadevall 33 Aug 20, 2022
Unofficial Python implementation of the DNMF overlapping community detection algorithm

DNMF Unofficial Python implementation of the Discrete Non-negative Matrix Factorization (DNMF) overlapping community detection algorithm Paper Ye, Fan

Andrej Janchevski 3 Nov 30, 2021
MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework

MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework, which facilitates the coordination of massively parallel multiscale simulations.

4 Aug 17, 2022
Render reMarkable documents to PDF

rmrl: reMarkable Rendering Library rmrl is a Python library for rendering reMarkable documents to PDF files. It takes the original PDF document and th

Robert Schroll 95 Dec 25, 2022
Better Giveaways is a bot that will change the experience of using a giveaway bot forever.

Better-Giveaways Better Giveaways is a bot that will change the experience of using a giveaway bot forever. VoxelBotUtils/Novus, latest PyPi releases

Lightning 2 Jan 12, 2022
An assistant to guess your pip dependencies from your code, without using a requirements file.

Pip Sala Bim is an assistant to guess your pip dependencies from your code, without using a requirements file. Pip Sala Bim will tell you which packag

Collage Labs 15 Nov 19, 2022
Python Programmma DarkMap.py

DarkMap Python Programmma DarkMap.py O'rganish va rasmlarni ko'riosh https://drive.google.com/drive/folders/1l1zybs_0Zy9z_trZYz5R72WrwsE6mFOh?usp=shar

Og'abek 0 May 06, 2022
A free website that keeps the people informed about housing and evictions.

Eviction Tracker Currently helping verify detainer warrant data for middle Tennessee - via Middle TN DSA - Red Door Collective Features Presents data

Red Door Collective 7 Dec 14, 2022
Button paginator using discord_components

Button Paginator With discord-components Button paginator using discord_components Welcome! It's a paginator for discord-componets! Thanks to the orig

Decave 7 Feb 12, 2022
InverterApi - This project has been designed to take monitoring data from Voltronic, Axpert, Mppsolar PIP, Voltacon, Effekta

InverterApi - This project has been designed to take monitoring data from Voltronic, Axpert, Mppsolar PIP, Voltacon, Effekta

Josep Escobar 2 Sep 03, 2022
B-Pkg is a simple tool in python for installing all basic package in termux

Basic-Pkg 👉🏻 Basic-Pkg 👈🏻 B-Pkg is a simple tool in python for installing all basic package in termux This is my first tool, I hope you will like

Macgaiver 3 Oct 21, 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
A inspector to be able to view and edit Qt style sheet while an application is running

Qt Style Sheet Inspector An inspector widget to view and modify the style sheet of a Qt app at runtime. Usage In order to use the inspector widget on

ESSS 46 Dec 10, 2022
🍕 A small app with capabilities ordering food and listing them with pub/sub pattern

food-ordering A small app with capabilities ordering food and listing them. Prerequisites Docker Run Tests docker-compose run --rm web ./manage.py tes

Muhammet Mücahit 1 Jan 14, 2022
Free components that wrap up Python into Delphi and Lazarus (FPC)

Python for Delphi (P4D) is a set of free components that wrap up the Python DLL into Delphi and Lazarus (FPC). They let you easily execute Python scri

747 Jan 02, 2023
Got-book-6 - LSTM trained on the first five ASOIAF/GOT books

GOT Book 6 Generator Are you tired of waiting for the next GOT book to come out? I know that I am, which is why I decided to train a RNN on the first

Zack Thoutt 974 Oct 27, 2022
Ferramenta de monitoramento do risco de colapso no sistema de saúde em municípios brasileiros com a Covid-19.

FarolCovid 🚦 Ferramenta de monitoramento do risco de colapso no sistema de saúde em municípios brasileiros com a Covid-19. Monitoring tool & simulati

Impulso 49 Jul 10, 2022
Anki Cards for the HSK vocabulary Chinese-German

Anki-HanyuShuipingKaoshi Anki Cards for the HSK vocabulary Chinese-German Das Deck baut auf folgenden Quellen auf: China Endecken Wortschatz von wohok

1 Jan 07, 2022
Script for resizing MTD partitions on a QNAP device in order to be available to upgrade from buster to bullseye

QNAP partitions resize for kirkwood devices. As explained by Marin Michlmayr, Debian bullseye support on kirkwood QNAP devices was dropped due to [mai

Arnaud Mouiche 26 Jan 05, 2023
Bitflip Fault Simulation Platform by Daniele Rizzieri (2021)

SEE Injection Framework 2021 This repository contains two Single Event Effect (SEE) injection platforms. The first one is called BFSP - "Bitflip Fault

Daniele Rizzieri 2 Nov 05, 2022