Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data
Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two of opposite types with probability $q$. For what values of $p, q$ can we recover the partition with high probability (with respect to $n$)? It turns out that if $p$ and $q$ are too close then it is statistically impossible, and otherwise a simple algorithm succeeds with high probability. 

The question you are asking is very specific, and the answer likely depends on the exact model and its parameters. It seems likely that for a low mutation rate, some iterative algorithm should work, perhaps even provably (with high probability).

One way to formulate this question more concretely is to come up with constraints on the relations between the sequences, constraints that hold with high probability. It could be that for an appropriate choice of constraints, the problem becomes feasible.