Find subsequence in matrix

user_10136694 0
Viewed 167

I was practicing in an online judge and I get this challenge, "Given a six-character string array (DNA string) find if has a mutation, you know if a mutation exists if you find a subsequence of 4 equals consecutive characters, you can find it vertically, horizontally and obliquely".

So If I have the next string array:

dna = { "ATGCGA", "CAGTGC", "TTATGT", "AGAAGG", "CCCCTA", "TCACTG" }

It may become a matrix like this:

ATGCGA
CAGTGC
TTATGT
AGAAGG
CCCCTA
TCACTG

It's important to note that the length of the string may not be 6 but have to be the same for all the array, to form an NxN matrix.

And the output from the algorithm should be true because it has three mutations.

AXXXXX
XAXXXX
XXAXXX
XXXAXX
XXXXXX
XXXXXX

XXXXXX
XXXXXX
XXXXXX
XXXXXX
CCCCXX
XXXXXX

XXXXGX
XXXXGX
XXXXGX
XXXXGX
XXXXXX
XXXXXX

Any of these mutations must make to the algorithm to return that it has a mutation.

I tried to apply the longest common subsequence by chaining the matrix into 3 different strings in other words a big column, a big row, and a big diagonal but it makes the efficiency of the algorithm the worst.

Could someone guide me?

dna-sequence sequence matrix algorithm
1 Answers

If we're just looking for a contiguous sequence of identical letters, we can solve this in O(min(m, n)) space and O(mn) time, where m is the number of rows and n the number of columns. Iterate row by row from the top left (for example). For each cell, record the number of contiguous cells above, to the left, and to the northwest, by adding 1 to the record for the neighbour in each respective direction if that neighbour has the same letter; otherwise, record 1.

(If we were looking for not-necessarily-contiguous subsequences, we could still solve it with the same complexity, provided the alphabet is fixed, but we'd then have to keep a state for each letter in each record.)

user_20347870
Related