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
A powerful and user-friendly binary analysis platform!

angr angr is a platform-agnostic binary analysis framework. It is brought to you by the Computer Security Lab at UC Santa Barbara, SEFCOM at Arizona S

6.3k Jan 02, 2023
A deployer and package manager for OceanBase open-source software.

OceanBase Deploy OceanBase Deploy （简称 OBD）是 OceanBase 开源软件的安装部署工具。OBD 同时也是包管理器，可以用来管理 OceanBase 所有的开源软件。本文介绍如何安装 OBD、使用 OBD 和 OBD 的命令。 安装 OBD 您可以使用以下方

OceanBase 59 Dec 27, 2022
用于导出墨墨背单词的词库，并生成适用于 List 背单词，不背单词，欧陆词典等的自定义词库

maimemo-export 用于导出墨墨背单词的词库，并生成适用于 List 背单词，欧陆词典，不背单词等的自定义词库。 仓库内已经导出墨墨背单词所有自带词库（暂不包括云词库），多达 900 种词库，可以在仓库中选择需要的词库下载（下载单个文件的方法），也可以去 蓝奏云（密码:666） 下载打包好

ourongxing 293 Dec 29, 2022
Service for working with open data of the State Duma of the Russian Federation

Сервис для работы с открытыми данными Госдумы РФ Исходные данные из API Госдумы РФ извлекаются с помощью Apache Nifi и приземляются в хранилище Clickh

Aleksandr Sergeenko 2 Feb 14, 2022
🌍💉 Global COVID-19 vaccination data at the regional level.

COVID-19 vaccination data at subnational level. To ensure its officiality, the source data is carefully verified.

sociepy 61 Sep 21, 2022
A Python script to parse Fortinet products serial numbers, and detect the associated model and version.

ParseFortinetSerialNumber A Python script to parse Fortinet products serial numbers, and detect the associated model and version. Example $ ./ParseFor

Podalirius 10 Oct 28, 2022
A Lego Mindstorm robot for dealing out cards based on a birds-eye view of a poker table and given ArUco fiducial tags.

A Lego Mindstorm robot for dealing out cards based on a birds-eye view of a poker table and given ArUco fiducial tags.

4 Dec 06, 2021
Participants of Bertelsmann Technology Scholarship created an awesome list of resources and they want to share it with the world, if you find illegal resources please report to us and we will remove.

Participants of Bertelsmann Technology Scholarship created an awesome list of resources and they want to share it with the world, if you find illegal

Wissem Marzouki 29 Nov 28, 2022
Paprika is a python library that reduces boilerplate. Heavily inspired by Project Lombok.

Image courtesy of Anna Quaglia (Photographer) Paprika Paprika is a python library that reduces boilerplate. It is heavily inspired by Project Lombok.

Rayan Hatout 55 Dec 26, 2022
Location of public benchmarking; primarily final results

CSL_public_benchmark This repo is intended to provide a periodically-updated, public view into genome sequencing benchmarks managed by HudsonAlpha's C

HudsonAlpha Institute for Biotechnology 15 Jun 13, 2022
A common, beautiful interface to tabular data, no matter the format

rows No matter in which format your tabular data is: rows will import it, automatically detect types and give you high-level Python objects so you can

Álvaro Justen 834 Jan 03, 2023
Verification of Monty Hall problem by experimental simulation.

Verification of Monty Hall problem by experimental simulation. |中文|English| In the process of learning causal inference, I learned about the Monty Hal

云端听茗 1 Nov 22, 2022
Monitor the New World login queue and notify when it is about to finish

nwwatch - Monitor the New World queue and notify when it is about to finish Getting Started install python 3.7+ navigate to the directory where you un

14 Jan 10, 2022
pybind11 — Seamless operability between C++11 and Python

pybind11 — Seamless operability between C++11 and Python Setuptools example • Scikit-build example • CMake example pybind11 is a lightweight header-on

pybind 12.1k Jan 08, 2023
run-js Goal: The Easiest Way to Run JavaScript in Python

run-js Goal: The Easiest Way to Run JavaScript in Python features Stateless Async JS Functions No Intermediary Files Functional Programming CommonJS a

Daniel J. Dufour 9 Aug 16, 2022
Experimental Brawl Stars v36.218 server emulator written in Python.

Brawl Stars v36 Experimental Brawl Stars v36.218 server emulator written in Python. Requirements: Python 3.7 or higher colorama Running the server In

8 Oct 31, 2021
Helps to arrange nodes

Relax brush for nodes, helps to arrange nodes easier.

336 Dec 15, 2022
This python script extracts all the video URLs from any youtube channel. Then it extracts all the information like the name of the youtube channel, published date, likes, dislikes, comments, views, etc for all the videos in that channel.

youtube-channel-video-url-extractor This python script extracts all the video URLs from any youtube channel. Then it extracts all the information like

Donatus Prince 6 Feb 25, 2022
Decentralized intelligent voting application.

DiVA Decentralized intelligent voting application. Hack the North 2021. Inspiration Following the previous US election, many voters were fearful that

Ali Shariatmadari 4 Jun 05, 2022
Simple python bot, that notifies about new manga chapters through Telegram.

Simple python bot, that notifies about new manga chapters through Telegram.

Dmitry Kopturov 1 Dec 05, 2021