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"
]
}
28 Dec 30, 2022
1.5k Nov 16, 2022
47 Jan 01, 2023
4.8k Jan 08, 2023
2 Jun 14, 2022
142 Jan 05, 2023
4 Oct 17, 2021
11 Dec 30, 2021
7 Mar 10, 2022
5 Mar 31, 2022
32 Nov 10, 2022
7 Jan 09, 2022
106 Dec 27, 2022
1 Dec 07, 2021
8 Nov 04, 2022
328 Dec 29, 2022
180 Oct 08, 2022
22 May 31, 2022
1 Nov 15, 2021
1 Jan 25, 2022