This repository contains an implementation of the Locally Consistent Parsing (LCP) algorithm, applied to strings using a specific binary alphabet encoding. The implementation is in C and is designed for efficient computation of LCP on large datasets.
For additional details about the data structure, please refer to this document.
- Efficient LCP Computation: Implemented in C for efficient and scalable computation on large datasets.
- High Accuracy: Achieves highly accurate comparisons by leveraging the unique LCP approach.
- Designed for Genomics: Specifically caters to the needs of genomic researchers and bioinformaticians.
You can install lcptools either system-wide (requires sudo privileges) or in a user-specific directory (no sudo required).
To install lcptools system-wide, you need sudo privileges. This will install the library in /usr/local.
-
Install the repository:
git clone https://github.com/BilkentCompGen/lcptools.git cd lcptools # Install the library sudo make install
-
Uninstall the library (if needed):
sudo make uninstall
To install lcptools in your home directory (or another custom directory), you don't need sudo privileges.
-
Install the repository:
git clone https://github.com/BilkentCompGen/lcptools.git cd lcptools # Install the library to a custom directory (e.g., `~/.local`):** make install PREFIX=$(HOME)/.local
-
Uninstall the library from the custom directory (if needed):
make uninstall PREFIX=$(HOME)/.local
To compile your program with your program, you need to specify the include and library paths based on your installation method.
If you want to link static library, please use as follows:
g++ your_program.cpp -static -llcptools -o your_programIf you want to link dynamic library, please use as follows:
g++ your_program.cpp -llcptools -o your_programIf you want to link static library, please use as follows:
g++ your_program.cpp -static -I$(HOME)/.local/include/lcptools -L$(HOME)/.local/lib -llcptools -o your_programIf you want to link dynamic library, please use as follows:
g++ your_program.cpp -I$(HOME)/.local/include/lcptools -L$(HOME)/.local/lib -llcptools -Wl,-rpath,$(HOME)/.local/lib -o your_programNote: Make sure that paths are correct.
The binary encoding of the alphabet is defined as follows. This default encoding is used unless a custom encoding is provided:
| Character | Binary Encoding |
|---|---|
| A, a | 00 |
| T, t | 11 |
| G, g | 10 |
| C, c | 01 |
To initialize the encodings, use the following function call at the beginning of your program.
LCP_INIT();In the above code, defaults the verbose to 0.
A integer parameter verbose can be provided, which, when set to 1, prints a summary of the encoding:
LCP_INIT2(verbose);To display the encoding summary separately, use:
LCP_SUMMARY();Below is an example demonstrating the usage of the LCP algorithm implementation:
#include "lps.h"
int main() {
// Initialize alphabet coefficients
LCP_INIT();
// Example string
const char *str = "GGGACCTGGTGACCCCAGCCCACGACAGCCAAGCGCCAGCTGAGCTCAGGTGTGAGGAGATCACAGTCCT";
// Create LCP string object
struct lps lcp_str;
init_lps(&lcp_str, str, strlen(str));
// Deepen the LCP analysis
int isSuccess = lps_deepen(&lcp_str, 2);
// Output LCP string
print_lps(&lcp_str);
// Clean up to prevent memory leaks
free_lps(&lcp_str);
return 0;
}The LCP algorithm operates as follows:
Processes the input string and identifies cores that adhere to specific rules:
-
(LMIN) The subsequent characters should not be the same, and the middle character is local minima.
Ex:
$w = xyz$ where$x \neq y$ and$y \neq z$ , and$x \gt y$ and$y \lt z$ -
(LMAX) The subsequent characters should not be the same, and the middle character local maxima, and its neighbors are not local minima.
Ex:
$w = sxyzt$ where$s \neq x$ and$x \neq y$ and$y \neq z$ and$z \neq t$ , and$s \leq x$ and$x \lt y$ and$y \gt z$ and$z \geq t$ . -
(RINT) The characters, except the front and back, are the same.
Ex:
$w=xy^iz$ where$i > 1$ and$|w| \gt 3$ , , and$x\neq y$ ,$y\neq z$ . -
(SSEQ) The subsequent characters are either strictly increasing or decreasing with respect to the lexicographic order, and only the first and last characters are part of either a LMIN, LMAX, or a RINT.
Ex:
$w = xyza_0 . . . a_nklm$ , where$n \geq 1$ and$xyz$ and$klm$ are identified as cores, and$z \lt a_0 \lt \dots \lt a_n \lt k$ or$z \gt a_0 \gt \dots \gt a_n \gt k$ .
The dct function in the LCP algorithm is crucial for processing binary sequences. It starts by pinpointing the initial point of difference between two binary strings, beginning from the right-end. The function then assesses the difference based on the position and value of the divergent bit. This detail is transformed into a new binary sequence, which establishes the foundation of a newly generated 'core'. This core is a clear representation of the differences between the original sequences, integral to the algorithm's deepening process. Essentially, the dct function effectively consolidates and encapsulates the information, ensuring efficient further analysis within the LCP framework.
Ex: 11101000 vs 00010100 -> 100 as the position is 2 (10) and the bit is 0. Position index start from 0.
The deepen function in the LCP algorithm primarily focuses on the compression of 'cores' alongside their left neighbors. The purpose of this repeated compression (dct) is to manage the length of the cores, preventing them from becoming large. After a compression, the LCP algorithm is re-applied. This re-application aims to identify new cores within the compressed data. In this context, each compressed core is treated as a discrete value, represented in binary form. This representation facilitates efficient processing and analysis within the algorithm.
This function iteratively compresses and processes cores to find new cores in compliance with the rules stated above.
The default iteration count for compression in each deepening is set to 1.