Neural Edit Operations for Biological Sequences
The evolution of biological sequences, such as proteins or DNAs, is driven by the three basic edit operations: substitution, insertion, and deletion. Motivated by the recent progress of neural network models for biological tasks, we implement two neural network architectures that can treat such edit operations. The first proposal is the edit invariant neural networks, based on differentiable Needleman-Wunsch algorithms. The second is the use of deep CNNs with concatenations. Our analysis shows that CNNs can recognize regular expressions without Kleene star, and that deeper CNNs can recognize more complex regular expressions including the insertion/deletion of characters. The experimental results for the protein secondary structure prediction task suggest the importance of insertion/deletion. The test accuracy on the widely-used CB513 dataset is 71.5%, which is 1.2-points better than the current best result on non-ensemble models.
Needleman-Wunsch algorithm [17] as a differentiable neural network. Next, we show that deep CNNs with concatenations can treat regular expressions without Kleene stars, indicating that such CNNs can capture edit operations including insertion/deletion. Our experiments demonstrate the validity of our approach. The test accuracy of protein secondary structure prediction on the widely-used CB513 dataset (e.g., [26]) results in 71.5% accuracy, the state-of-the-art performance compared to those of previous studies on non-ensemble models. Differentiable Sequence Alignment. In bioinformatics, sequence alignment is key in comparing two biological strings (e.g., DNA, proteins). The NeedlemanWunsch (NW) algorithm [17], a fundamental sequence alignment algorithm, calculates the similarity score between two strings on an alphabet Σ. As shown in Fig.  1, the similarity score is computed via dynamic programming to maximize the total score (illustrated as the double-lined square) by inserting or deleting characters (depicted as the vertical and horizontal arrows, respectively).
This manuscript describes two methods for representing sequence editing operations in neural networks. The authors are motivated by problems in bioinformatics, in which insert, deletion and substitution operations represent basic moves in sequence evolution.  The two techniques are complementary: one replaces the inner loop of the neural net training with a differentiable version of the Needleman-Wunsh dynamic programming algorithm; the other describes a general method for constructing convolutional network architectures that represent a particular class of regular expressions.  Each approach has its drawbacks.  The first method is elegant but computationally expensive; the second method naturally leads to very large networks, requiring some hoop-jumping in order to get the networks down to a more reasonable size. The authors demonstrate the utility of both methods on a small example, and then show that the CNN approach can lead to state-of-the-art results on the prediction of protein secondary structure.  Overall, this manuscript was a pleasure to read, and the core ideas are compelling.  It is certainly the case that deep architectures are being applied more and more widely within bioinformatics, and creative ways to represent sequence operations in this domain are likely to be of very wide interest.  One concern I have is about the experimental results: the authors misrepresent their achievement relative to the state of the art.  In the abstract they explicitly state that they have improved on the state of the art by 1.2% in accuracy.  This is simply false, as pointed out in the footnote on p. 6: they have only improved on non-ensemble models by 1.2%.  The best ensemble method achieves an accuracy only 0.1% less than the method reported here.  The artificial choice to exclude ensemble methods is completely unmotivated. Indeed, there is no reason the authors could not have created ensembles of their own method.  A second considerable caveat to the experimental results is that the authors have clearly and explicitly engaged in data snooping on the CB513 benchmark.  The manuscript reports results from a wide variety of models on this benchmark, and presumably others were tried as well. As such, these results are likely overfit to this benchmark.  To truly show that they have achieved the state of the art, the authors should have used an independent benchmark to do model development and then run only the best-performing method on CB513.  One drawback to the first contribution (EINN) is that the Needleman-Wunsch algorithm is not, actually, widely used at all in bioinformatics. First, any DP algorithm for biosequence alignment needs to be generalized to use affine gap costs (i.e., charge more for introducing a new gap than for extending an existing gap).  Second, only in rare cases is a global alignment required; it is much more common to use a local alignment algorithm like Smith-Waterman. The authors claim on line 211 that they can also apply the EINN method to SW, but this should be done or at least mentioned earlier. Third, in practice, both NW and SW are too slow for most bioinformatics applications, so heuristic approximations like BLAST are much more widely used.  Given these caveats, the description of NW as "one of the most heavily-used sequence alignment algorithms" (line 43) is incorrect and misleading. Note that I don't see any conceptual reason why the proposed method could not be extended to affine gap penalties and local alignment; only that the authors should (1) admit that the method they have implemented falls short of capturing what is used in practice, and (2) at least sketch how the method could be extended to these other settings.  Another concern regarding the empirical results is the "data augmentation" strategy proposed on lines 272-280. The method consists, essentially, of adding noisy versions of the training examples to the input. It is surprising that this method helps, and if this techniques actually accounts for up to 0.8% of the observed improvement, then it is just as important as the star-free regular expression CNN stuff that is purported to be the main advance in this part of the paper.  The authors should discuss the motivation for this technique in more detail.  The writing throughout is clear, though the text exhibits numerous grammatical and usage errors.  I list some of these below, but the authors are encouraged to identify others as well.  The definite or indefinite article is misused (included where not needed, skipped where needed, or wrong type of article) in lines 42, 63, 77, 107, 116, 126, 155, 231, 232.  12: delete "of"  79: Delete "of the."  137: "accepting" -> "accepts"  144: "star" -> "stars"  171, 203: The verb "allow" requires a direct object.  186: Semicolon before "however."  214: "neuron" -> "neurons"  Figure 3: "Concatination" -> "Concatenation"  119: "does" -> "means"  242: "reminder" -> "remainder"  297: "of EINN" -> "for EINNs"  304: "indicates the time complexity" -> "yields a time complexity of"  Other minor comments:  35: Briefly define "star-free regular expression" here.  37: State that CB513 is for protein secondary structure prediction.  101: Delete the sentence beginning "Therefore, ..." (It is obvious, given the previous sentence).  187 "Real biological tasks": Did the authors evaluate the method on tasks other than secondary structure prediction? Mention details here.  I read the author response, and it seemed reasonable. I do think the paper has some problems with the empirical evaluation (as also commented on by Reviewer #2), but they are not fatal flaws. Hence, I did not modify my score.