CRISPR cassettes − reconstruction of symbol sequences from observed subsequences with bioinformatics applications

<div>This study examines CRISPR (Clustered, Regularly Interspaced Short&nbsp;</div><div>Palindromic Repeats) cassettes which are special parts of genome. CRISPR&nbsp;</div><div>systems provide defensive function and have similar structural features. Presented&nbsp;</div><div>work performed as the part of the joint project with A. Lipnyagov supported by&nbsp;</div><div>RTCB IITP RAS and describes analysis of existing information about CRISPR&nbsp;</div><div>systems using mathematical approaches. The paper examines in detail the creation&nbsp;</div><div>of the special object for every group of CRISPR cassettes with similar structural&nbsp;</div><div>characteristics. The problem of building such object belongs to NP class, and the&nbsp;</div><div>study describes heuristic approaches for real data solution, in particular 4-</div><div>approximation algorithm. It was necessary to find all of the exact solutions of this&nbsp;</div><div>problem and the study describes approaches and methods for it using several&nbsp;</div><div>sequence-based graph algorithms.&nbsp;</div><div>&nbsp;</div>