3
$\begingroup$

Given the sequence of symbols $A$ (contains ~10,000 symbols) and sequence of blocks $B$ (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence $B$ so that symbols inside sum of blocks from $B$ will be equal to $A$. Blocks cannot be modified or replaced, they have fixed position in sequence.

Sequences example

I'm looking for some computation efficient method to solve this problem as Levenshtein distance looks too expensive for this task. Besides, Levenshtein distance works with individual symbols, it is not entirely clear how to move from block to symbols in this case.

Some obvious ideas:

  • If sequence $A$ does not contain block $b_i$, then $b_i$ can be excluded from $B$
  • If there are no blocks inside $B$, that are subsequences of $b_i$ and $b_i$ is the only match to subsequence $a_j$, the whole task can be split into two separate pieces
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

A modification of Needleman–Wunsch algorithm for global alignment of $A$ and $B$, where you match/skip whole blocks (rather than individual symbols) in $B$ and do not allow gaps in $A$, will do the job. The running time is proportional to product of sizes of $A$ and $B$.

P.S. Is this a homework problem by any chance?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ P.S.not a homework. I'm working on mapping the html formatting to the extracted text - this field is a bit far from bioinformatics. $\endgroup$
    – ilia
    Sep 6, 2018 at 13:35
  • 1
    $\begingroup$ @ilia: OK, good luck! I'll borrow this problem for my bioinformatics class ;) $\endgroup$
    – Max Alekseyev
    Sep 6, 2018 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.