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

Auto check in via GitHub Actions

Бэкапалка таблиц mysql 8 через брокер сообщений nats

Auto-ropper is a tool that aims to automate the exploitation of ROP.

Simple Assembler with python

Pytorch implementation of "Peer Loss Functions: Learning from Noisy Labels without Knowing Noise Rates"

ASCII-Wordle - A port of the game Wordle to terminal emulators/CMD

Unofficial package for fetching users information based on National ID Number (Tanzania)

💡 Fully automatic light management based on conditions like motion, illuminance, humidity, and other clever features

清晰易读的7x7像素点阵中文字体和取模工具

An AddOn storing wireguard configuration

🙌Kart of 210+ projects based on machine learning, deep learning, computer vision, natural language processing and all. Show your support by ✨ this repository.

Open-source data observability for modern data teams

A tool to determine optimal projects for Gridcoin crunchers. Maximize your magnitude!

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

A toolkit for developing and deploying serverless Python code in AWS Lambda.

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

Simple Denial of Service Program yang di bikin menggunakan bahasa pemograman Python,

This repository requires you to solve a problem by writing some basic python code.

Expose multicam options in the Blender VSE headers.

Git Hooks Tutorial.