Glossary

Interwoven Strings

We say that strings $t$ and $u$ can be interwoven into a larger string $s$ if there is a substring $s'$ of $s$ whose symbols are formed of $t$ and $u$ as disjoint subsequences; that is, every symbol of $s'$ must appear in $t$ or $u$, and the same symbol of $s'$ cannot derive from both $t$ and $u$.

For example, the strings "$\color{blue}\text{ACAG}$" and "$\color{red}\text{CCG}$" can be interwoven into "$\color{black}\text{G}\color{blue}\text{A}\color{red}\text{C}\color{blue}\text{CA}\color{red}\text{C}\color{blue}\text{G}\color{red}\text{G}\color{black}\text{TT}$". However, they cannot be interwoven into "$\color{black}\text{G}\color{blue}\text{A}\color{red}\text{C}\color{blue}\text{CA}\color{red}\text{C}\color{black}\text{AAAA}\color{blue}\text{G}\color{red}\text{G}\color{black}\text{TT}$" because of the appearance of the four 'A's in the middle of the subsequences.

If two DNA strings can be interwoven into a genome, then they may represent coding regions of disjoint genes.