Assembling genomes: From Composition to Paired Composition

Notation of paired compositions

Given a string Text, a (k, d)-mer is a pair of k-mers in Text separated by distance d. We use the notation (Pattern$_{1}$ | Pattern$_{2}$) to refer to a (k, d)-mer whose k-mers are Pattern$_{1}$ and Pattern$_{2}$. For example, (AAT | TGG) is a (3, 4)-mer in TAATGCCATGGGATGTT. The (k, d)-mer composition of Text, denoted PairedComposition$_{k, d}$ (Text), is the collection of all (k, d)-mers in Text (including repeated (k, d)-mers). For example, here’s PairedComposition$_{3,1}$(TAATGCCATGGGATGTT):