Collapse a set of redundant kmers to use IUPAC degenerate bases

Last update: Jan 06, 2022

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"
    ]
}

Collapse a set of redundant kmers to use IUPAC degenerate bases

Related tags

Overview

kmer-collapse

Overview

Usage

Notes

Examples

A

B

C

D

E

F

G

Owner

Alex Reynolds

Home Assistant integration for spanish electrical data providers (e.g., datadis)

py-js: python3 objects for max

List of Linux Tools I put on almost every linux / Debian host

A middle-to-high level algorithm book designed with coding interview at heart!

Example of my qtile config using the gruvbox colorscheme.

It is a Blender Tool which can convert the Object Data Attributes in face corner to the UVs or Vertex Color.

The calculator on Python.

A set of decks and notebooks with exercises for use in a hands-on causal inference tutorial session

The code behind sqlfmt.com, a web UI for sqlfmt

A web-based analysis toolkit for the System Usability Scale providing calculation, plotting, interpretation and contextualization utility

A collection of Python library code for building Python applications.

Better Giveaways is a bot that will change the experience of using a giveaway bot forever.

A fast python implementation of DTU MVS 2014 evaluation

Autogenerador tonto de paquetes para ROSCPP

Distribute PySPI jobs across a PBS cluster

SECRET SANTA / KRIS KINGLE

This interactive script demonstrates the Menezes-Vanstone-EC-Cryptosystem

An Notifier Program that Notifies you to relax your eyes Every 15 Minutes👀

Inviare messaggi tramite app IO a partire da dati contenuti in file .csv

Small tool to use hero .json files created with Optolith for The Dark Eye/ Das Schwarze Auge 5 to perform talent probes.