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"
]
}
3 Sep 19, 2022
0 Apr 22, 2022
1 Dec 13, 2021
771 Dec 29, 2022
3 Dec 13, 2021
3 Nov 08, 2022
20 Dec 27, 2022
90 Jan 01, 2023
5 Jun 04, 2021
4 Sep 20, 2022
13 Sep 07, 2022
1 Jan 12, 2022
5 Feb 19, 2022
1 Mar 04, 2022
19 Jun 03, 2021
3 Aug 11, 2022
1 Dec 22, 2021
3 Dec 06, 2022
3 May 30, 2022
3 Jan 25, 2022