Data-Driven Application Maintenance: Views from the Trenches

In this paper we present our experience during design, development, and pilot deployments of a data-driven machine learning based application maintenance solution. We implemented a proof of concept to address a spectrum of interrelated problems encountered in application maintenance projects including duplicate incident ticket identification, assignee recommendation, theme mining, and mapping of incidents to business processes. In the context of IT services, these problems are frequently encountered, yet there is a gap in bringing automation and optimization. Despite long-standing research around mining and analysis of software repositories, such research outputs are not adopted well in practice due to the constraints these solutions impose on the users. We discuss need for designing pragmatic solutions with low barriers to adoption and addressing right level of complexity of problems with respect to underlying business constraints and nature of data.

Introduction
Ticket or Incident Management is an important ITIL [9] process, where an incoming ticket logged by the users of the system is analyzed and appropriate measures are taken for remediation within pre-specified time constraints. In terms of an activity pipeline, the tickets are first triaged, starting with a check for duplication so that one does not start working on a ticket which has already been closed or remediated, the tickets are then clustered based on themes around business process or techno-functional areas [7]; further, the tickets are assigned to service engineers who have already worked on similar incidents or technology; the service engineers may take recourse to knowledge management tools which may help them to resolve the problem in a guided way by providing contextual search facility on product knowledge base or literature [10].
Volume of research has been conducted on each of the steps of the process. The problem of triaging and identifying duplicate incidents or tickets has been discussed in [14], especially in the context of mining large-scale open source and other software repositories and developer comments. Mapping to business processes has been studied in [8]. Recommendation of assignee has been discussed in [13].
While there is no dearth in investigation on and application of advanced techniques like Machine Learning (classification and clustering), Natural Language Processing and Guided Search; in practice, the problem remains largely unsolved. There are several contributing factors that make "in the trench" application of sophisticated technologies challenging. We list a few of them The data conundrum Industry data is either very noisy or very sparse. This is especially true when the systems have wide variety of applications and usage scenarios. This makes data sampling and preparation for machine learning fairly difficult.
SME support Most classification techniques would require proper identification of features which are discriminating enough to render the data set classifiable. Often times, we find that these discriminating features are buried in the semantics of the description and it becomes very difficult for a data-scientist to conduct proper feature engineering without help from the subject matter experts (SMEs) to understand the semantics. However, the SMEs may often not have enough time to support.
Cost and Time to market In practice, for the solution to be usable, the time to maturity would have to be short and implementable without much penalty in terms of cost and time. This is because such systems are often used to augment the support engineers, who may not have enough expertise and training to deal with intricacies.
In this report, we describe a "shop usable" for some aspects of the incident management problem and share experience from the implementation details. We believe that this paper would illustrate the contours and challenges of a practical research where unsupervised semantic similarity and ML techniques have been deployed to provide good enough solution. We also share some thoughts on the challenges for roll-out and feedback from the actual users of this incident management system.
Notations: In the rest of the paper, we will use 'ticket', 'incident', and 'bug' interchangeably. The PoC prototype tool will be referred henceforth as CogAM (Cognitive Application Maintenance).

Bug Deduplication: Identify Similar Incidents
Current Scenario: When a new ticket is logged, users need to search existing ticket logs to find out if a duplicate bug has been already resolved/closed in past. Effectiveness of the search process not only depends upon nature of search query in relation to existing ticket log data but also on knowledge and expertize of the user. Even though existing application maintenance (AM) tools (e.g., Remedy citeremedy, ServiceNow [3]) offer many features to manage incidents and other associated

Theme Mining
Identify Central Problem Areas Figure 1: Problem Scenarios processes, they fall short when it comes to offering plain text based semantic relevance search (often found in the realm of search engines). This makes it hard for users having relatively less experience to determine if semantically similar defects have already been raised in past and what actions were performed for those bugs. Solution Idea: In order to keep barriers to adoption low, we adopted IR (information retrieval) based solution (similar to [6]) by aiming to enable search based bug deduplication and identification of semantically related incidents. IR based approaches are largely unsupervised in nature, hence saving initial efforts from SMEs towards training the tool and appear to solve deduplication problem in AM domain at right level of complexity. It's success is based upon implicit assumption that if two bugs are similar (or related), they would have overlapping surface form representations (ref. 'distributional hypothesis' []).
Solution starts with generating a temporal informational model of incidents and their associations with assignees, business processes, and other semantically relevant factors. This model is used to estimate strengths of semantic associations to recommend related incidents (including duplicates), suggest assignees, identify potential business process associations, and pointers to potential resolutions. Ability to learn incrementally is designed to improve relevance of results from user interactions. Performance of CogAM could be improved further if it is coupled with domain knowledge sources, e.g., alias glossary consisting of synonymous terms.

Mapping Tickets to Business Processes
Current Scenario: When a new ticket is logged in an AM tool, SME may map reported incident to specific business process as a starting point to provide right level of intervention. Correctness of mapping primarily depends upon knowledge and expertize of the SME in conjunction with the degree of comprehensiveness of business process documentation. Solution Idea: Using existing log of tickets and associated business process mappings as recoded in the ticket log, CogAM would learn semantic associations between tickets and business processes by way of generating a ML model. When a new ticket arrives, CogAM would identify most probable business process, which current ticket should be mapped to and would recommend that to user. Based upon user acceptance or rejection of the recommendation, CogAM incrementally learns and improves its performance on the ticket mapping process.

Assignee Recommendation
Current Scenario: When a new ticket is logged, based upon expertize, availability, and other factors, suitable team member is selected and ticket is assigned to him/her for resolution. If an AM tool has to be used for an automated assignment, it requires manual configuration of parameters and tickets in the AM tool. However, stateof-the-art AM tools ignore historical evidence from past experience of working on similar tickets and are generally designed as rule based systems.
however, current practice is far from being optimal. From discussions with SMEs it turned out that when team sizes are not small (¿ 20) and ticket influx rates are high (¿ 50 per week), not always first time fixes of tickets were found to be correct and for 12-15% occasions tickets were either reopened owing to incorrect fixes or got reassigned to different team member.
Solution Idea: When a new ticket arrives, CogAM parses its details and would identify potential relationship with currently available team members (having worked in past) to map the ticket to those team members who could potentially be assigned to it because they worked on similar tickets in past. CogAM would produce a ranked list of team members so that right decision could be made even when the most suitable team member is not available. Based upon user acceptance or rejection of the recommendation, CogAM would incrementally learn and improve its performance on the assignment process. Performance of CogAM could be improved further if it is coupled with domain heuristics (e.g., documented expertize of the team members).

Theme Mining: Identifying Central Problem Areas
Current Scenario: When a ticket is raised, it may sometimes get tagged against high level functionality or component of the system or type of error potentially underlying the bug. Beyond this tagging, getting any further insights on the problem areas around which bugs are being raised remains limited to subjective experiences of the SMEs.
Large scale collective analysis of ticket text is necessary to identify central problem areas around which bugs are being raised over a course of time and semantic relationships among these problem areas.
Such insights enable better decision making towards allocating resources during design of newer versions of the applications and also during their maintenance.
Solution Idea: Using existing log of tickets CogAM applies combination of theme mining techniques including topic modelling, frequency based centrality, latent semantic analysis based centrality [12] on the terms (noun phrases and verb phrases) extracted from the bug data. Based upon that it would identify central terms with at least 85% bug coverage and their spread within user defined tagging (e.g., within modules).

Tool Design
CogAM is implemented as web application in Java using Spring MVC architecture [4]. User experience is the most important thing in any application. We used AdminLTE template [2] that is built on Bootstrap 3, JSP and JQuery to make user interface (UI) more user friendly, responsive and informative. We use Apache Lucene [1] for indexing and retrieving data and OpenNLP [5] for natural language processing. The high level architecture is shown in Figure 2. The first step is to con- figure fields that are used to retrieve data and apply filters to refine search results. Tool provides some fields as pre-defined fields like Incident Id, Short description, Long Description etc. Beyond these, tool allows users to define custom fields as per business requirements. Figure 3 describes filed configuration.
A field can be marked as information type where details of that particular field will be available in output screen or filter type with filter level where the field can be used as filter during search to refine results as per the requirements of the user. Filter level is used to define filter hierarchy e.g. Country, State, City is filter hierarchy while providing address details.
The second step is to ingest data. The tool supports MS Excel format for input data. Table 3 presents input data model, in which inputs to the designed tool need to be given as inputs.
Fields with plain-text details are of primary interest in this paper: (i) short description of an incident, (ii) detailed description of the incident, and (iii) reproduction steps.
The tool expects users to map fields to MS Excel columns. Also, users can configure name of the worksheet, date and time for data ingestion as shown below:   Once the data is ingested then tool is ready for providing ranked list of similar tickets for a new bug, details of which are given to the tool as search query. Here user can apply filters if configured earlier and narrow down search by applying date range as shown below: The results are categorized into four classes and users can get details of each output. The threshold of those four categories were decided based on empirical studies performed internally on various data sets.

Pilot Studies and Observations
For experimental analysis, PoC tool was given to SMEs for evaluation in their actual practice from multiple client accounts spread across various industries including retail, leisure, energy and petrochemicals, and mining. In each case, we asked SMEs to consider multiple projects satisfying one or more of the following requirements: 1. Rate at which bugs are being raised are not very low (¡ 10 per week) 2. Historical bug data-base contains at least 100 tickets 3. Degree of redirection of bugs is at least 10% i.e., bugs are not getting closed correctly for at least 10% cases

Identifying Semantically Similar Bugs
Nature of Data: Most of the time only single line details were available as bug description apart from information on other fields (see Table 1). Detailed descriptions were not available in all cases or were not very different from brief descriptions. Resolution notes or root cause analysis or steps to reproduce bugs were also often missing or were very brief or very extensive involving detailed communication which took place (often using emails) among team members while resolving bugs.
Additionally, plain text descriptions contained specific symbols (e.g. '#* ... *#') to enclose terms (meaning of which known only within team) as visual clues about the nature of bugs. Sometime bugs having exactly same text but differing in these localized terms were considered semantically related but not duplicate by SMEs. Also, during experimental analysis of many other use cases it turned out that such code words contained critical semantic information, however, this was something not possible to extract without SME help.
Experimental Analysis: Table 2 presents results from a pilot study with a retail account, wherein tool was injested with ticket log of nearly twenty six thousand incidents and SMEs designed 59 sample bugs as queries based upon recent tickets which were not part of the ingested ticket log and evaluated relevance of the outputs from the tool from view point of resolving these bugs. Since it was not known to SMEs how many relevant bugs actually existed in the ticket log, only precision of the outputs at two different levels (top 5 and top 20) was measured.

Relevant Results Relevant + Related Results
Top 5 67% 71% Top 20 61% 69% In practice, domain familiarity and past experience of the users mattered a lot and often junior team members which were in sizable numbers, needed help from senior team members to figure out how to start understanding a bug. Therefore, when we asked them to use the tool, their primary requirement was that tool should be able to provide critical clues regarding a new bug, which otherwise would have come from senior SMEs.
From operational perspective, users across levels appreciated that tool had small learning curve and one could start using it right away after installation with minimal configuration requirements.
Challenges in Adoption of Research: When authors were designing the solution, it was not clear whether we need to adopt techniques which are claimed to be achieving best performance on open source data sets( [11]) for the problem of duplicate defect identification. Interestingly most of the published works with high scores in detecting duplicate bugs apply supervised machine learning techniques (including deep learning), which though work well on large open source data sets, however, can't be easily adopted in practice without incurring significant cost to create desired training data in form of semantically equivalent pairs of bugs by the experienced SMEs before tool could be adopted in practice. Interestingly, parallel efforts were in place in some other client account towards adoption of such supervised ML based tools and in detailed comparative analysis, it turned out that our PoC tool was only 5% below the other tool in performance (precision of top 20 relevant bugs for a new bug). On the other hand, simpler approaches based upon information retrieval methods have also been found to be reasonably effective in industrial settings [6] and our experience confirms this.

Assignee Recommendation
Nature of Data: Most often ticket data only contains name or employee ID of the team member who raised and/or fixed a bug. However, when a team member is selected for an assignment, external factors like documented skills as recorded in HR databases, team-organization, current work load, etc. also play very important role in decision making process, which however are not recorded as a part of ticket details.
Requirements for Minimal Solution: A solution which brings additional insights from the analysis of historical evidence received positive attention from the AM management. Time based filtering options were found to be of specific help since in many cases, at least some similar or related bugs had been fixed during recent past and older bugs might have been fixed by those who were no longer part of the team currently.
Experimental Analysis: Table 3 presents results from pilot studies from three different industry accounts with varying ticket log sizes. In each case, we randomly identified more than 30 existing tickets from each log for validation purpose and estimated accuracy of predicting assignee when compared with the actual assignment as recorded in the log data. One challenge in this analysis is that our target set is relatively narrow (among many capable team members, only one is listed in the log-data set and we need to predict that!) Primary reason for adopting this intrinsic validation as against SME based validation was that SMEs expressed their lack of familiarity with the team members who worked long back and in some cases teams had just acquired the contract to maintain the application from another firm, hence SMEs did not have much knowledge to validate outputs. Realizing that on aver-  Table 3: Average accuracy in predicting assignee using historical log as reference data age results were relatively poor, we investigated this further to learn whether there existed any correlation between number of tickets which were assigned to a team member and accuracy in being able to predict that team member as recommended Figure 7: Graphical representation of association between tickets on which a team member has worked and accuracy in prediction of that team member during validation assignee during validation. Graph 7 depicts that visually and as a numerical indicator, Pearson correlation coefficient between these factors was estimated as 0.34, which clearly indicated that higher number of assigned tickets to a team member may not imply higher accuracy in predicting whether a team member should work on a ticket. This could be owing to the factors which were not recorded in the ticket log, however were playing key role during ticket assignment. Challenges in Adoption of Research: Despite the fact that there exist many published research works on this problem, in practice today, often ad-hoc approaches reflecting prevailing organizational processes and practices are to be found. One reason for this is that often there are some transient and circumstantial factors, which affect the decision making process. Hoever, such factors are not recorded in a way that these could be given as inputs to a tool. For example, consider the role of training programs, which play a role while assigning tickets to those team members who had undergone training on related functional areas recently. However, it would be hardly captured in an AM tool. This became further evident when we tried training a ML model on the ticket log (using features from vector space modeling and TF-IDf based information theoretic weighing) and Table 4 presents the results. It is clear from these results that ticket details as captured in the AM tool are hardly sufficient for achieving high accuracy in automated assignee recommendation. However, in practice, these outputs can still add value in assisting users in making informed decisions.
Size of Number of P R F1-Score Ticket Log Assignees 5600 28 0.35 0.31 0.33

Theme Mining
Nature of Data: Ticket log data often contains primary classification of the bugs in terms of modules or types of bugs. However, it misses giving any further insights, which can only be gleaned by detailed analysis of the bug descriptions, priority levels, number of re-directions, priority-escalations etc.
Requirements for Minimal Solution: Themes or central problem areas must be extracted such that their correlations with user categorizations are explicit. Furthermore, tool must provide detailed navigation support so that users get explanatory support underlying extracted results by the tool. For example, if a tool depicts that a problem area p = 'page access issue' is weakly connected with problem area q = 'password reset' but is strongly connected with r = 'login failure', user should be given underlying justification in terms of displaying list of tickets where first pair of problem areas (p, q) appear together versus where second pair (p, r) of problem areas appear in the ticket log.
Experimental Analysis: Table 5 shows results of various techniques, which we experimented with for mining central problem areas using examples ticket log consisting of twenty six thousand ticket details. Considered techniques included including latent semantic analysis based centrality; latent Dirichlet allocation; term frequency, and term frequency and inverse document frequency based centrality. Themes were extracted using textual fields as source of analysis. These themes were mined and analyzed for whole ticket-log and compared with project SMEs specified tagging. Precision of mined themes was not considered since SMEs were not available for analysis of the results and it would have been incorrect to assume that any theme not present in user specified tags must be considered wrong.

Approach
Recall  Challenges in Adoption of Research: As can be seen from relatively poor results in Table 5, primary challenge in adoption of existing approaches (mostly unsupervised in nature) is that they do not appear to align well with users' expectations. Alternative approaches which aim at filling this gap are supervised ML based approaches, which however require significant amount of annotated data to start with.

Business Process Mapping
Nature of Data: In practice, it turned out that often mapping of bugs with standard business processes is not mentioned and only proxy mappings with modules or components are recorded in AM tools. However, in case of large scale applications, it can be assumed that component or module level architecture approximately aligns with underlying business process hierarchy and relationships. Furthermore, assuming that business process maps are generally represented as a tree (acyclic undirected graph), it is sufficient to consider leaf level business process nodes (i.e., business process steps) alone as representative for who business process flow-path.
Experimental Analysis: Table 6 shows results of ML based prediction approach for associating business processes for tickets based upon learning from historical log data. We employed 10-fold cross validation as evaluation measure and experimented with six different data sets from different industry accounts with sizes of ticket logs ranging from 448 to 22000.  Noticing that performance of the tool was comparatively poorer in Data-Set#5, we investigated the cases where tool predicted incorrectly and it turned out that in most of the cases, bug description, which formed primary feature space for the ML technique, consisted of cryptic terms (often unique) like 'Kfeil: JSP045ABCD #ABCDD11759 [(231630 07/32/15), (0AAAAAAAAAAXXZW2M2U)]. ABCD1168 (#J137891)'. We extended this analysis to other Data-Sets as well and realized that presence of such terms, which can't be parsed without SME intervention, was primary source of errors in outputs.
Challenges in Adoption of Research: Application of supervised ML based approach resulted into comparatively better results and could be adopted in practice if designed as a separate tool which works in conjunction with existing AM tools. However, close integration with AM tools is not always possible since not all proprietary tools expose APIs for automated data export and in those cases, manual efforts in exporting data from AM tool and feeding it into tools like CogAM is necessary.

Threats to Validity
Even though we tried working with multiple industry accounts and had variety of data to analyze, it might still be limited by way of being influenced by circumstantial organizational factors which determined the nature of projects which we could work with currently. Furthermore, nature of software applications' data is a highly dynamic in nature and hence temporal reliability of the results would definitely demand ongoing reevaluations.

Conclusion and Future Work
In this paper, we discussed experiences with a data-driven application maintenance tool called CogAM, which applies information retrieval based semantic search technology and unsupervised / supervised machine learning approaches for addressing spectrum of interrelated problems in AM domain. In specific, we tackle the critical problems of checking duplicate incidents, assignment of tickets to appropriate resources, mining the central themes for a cluster of incidents, and mapping incidents to the underlying business processes.
Today, each of these tasks are carried out manually with considerable inefficiency and cost. While some of these problems have been researched extensively with sophisticated techniques on open source repositories and boards like Apache Foundation or Stack Overflow; we hardly find them to be shop usable as they impose challenges for adoption. Approach and tool has been piloted in real customer projects and we have received valuable lessons in terms of fitment, usability and adoption. Our experience suggests that in some cases search based solutions are good enough while in others detailed machine learned classifiers with annotated data would provide better results. Still in others, the problem becomes difficult as the ticket data as a single source of information is not enough to perform the necessary tasks which depend on external circumstantial inputs. In all cases, a richer domain knowledge becomes a key ingredient to success.
In future, we propose to carry out research in two main directions. First, there is clear need to carry out extensive experimentation with mass deployments to study the problem patterns across different types of maintenance projects and gather further insights. Second, we realize that rather than using pre-trained models, it would be better to experiment with active learning approaches where the engineers can interact and provide iterative supervision for better contextual refinement.


Grammatical Error Correction with Neural Reinforcement Learning

We propose a neural encoder-decoder model with reinforcement learning (NRL) for grammatical error correction (GEC). Unlike conventional maximum likelihood estimation (MLE), the model directly optimizes towards an objective that considers a sentence-level, task-specific evaluation metric, avoiding the exposure bias issue in MLE. We demonstrate that NRL outperforms MLE both in human and automated evaluation metrics, achieving the state-of-the-art on a fluency-oriented GEC corpus.

Introduction
Research in automated Grammatical Error Correction (GEC) has expanded from token-level, closed class corrections (e.g., determiners, prepositions, verb forms) to phrase-level, open class issues that consider fluency (e.g., content word choice, idiomatic collocation, word order, etc.).
The expanded goals of GEC have led to new proposed models deriving from techniques in data-driven machine translation, including phrasebased MT (PBMT) (Felice et al., 2014;Chollampatt et al., 2016;Junczys-Dowmunt and Grundkiewicz, 2016) and neural encoder-decoder models (Yuan and Briscoe, 2016). Napoles et al. (2017) recently showed that a neural encoderdecoder can outperform PBMT on a fluencyoriented GEC data and metric.
We investigate training methodologies in the neural encoder-decoder for GEC. To train the neural encoder-decoder models, maximum likelihood estimation (MLE) has been used, where the objective is to maximize the (log) likelihood of the parameters for a given training data.
As Ranzato et al. (2015) indicates, however, MLE has drawbacks. The MLE objective is based on word-level accuracy against the reference, and the model is not exposed to the predicted output during training (exposure bias). This becomes problematic, because once the model fails to predict a correct word, it falls off the right track and does not come back to it easily. To address the issues, we employ a neural encoder-decoder GEC model with a reinforcement learning approach in which we directly optimize the model toward our final objective (i.e., evaluation metric). The objective of the neural reinforcement learning model (NRL) is to maximize the expected reward on the training data. The model updates the parameters through back-propagation according to the reward from predicted outputs. The high-level description of the training procedure is shown in Algorithm 1, and more details are elaborated in §2. To our knowledge, this is the first attempt to employ reinforcement learning for directly optimizing the encoder-decoder model for GEC task.
We run GEC experiments on a fluency-oriented GEC corpus ( §3), demonstrating that NRL outperforms the MLE baseline both in human and automated evaluation metrics.

Model and Optimization
We use the attentional neural encoder-decoder model (Bahdanau et al., 2014) as a basis for both NRL and MLE. The model takes (possibly ungrammatical) source sentences x ∈ X as an input, and predicts grammatical and fluent output sentences y ∈ Y according to the model parameter θ. The model consists of two sub-modules, encoder and decoder. The encoder transforms x into a sequence of vector representations (hidden states) using a bidirectional gated recurrent neural network (GRU) (Chung et al., 2014). The decoder predicts a word y t at a time, using previous token y t−1 and linear combination of encoder information as attention.

Maximum Likelihood Estimation
Maximum Likelihood Estimation training (MLE) is a standard optimization method for encoderdecoder models. In MLE, the objective is to maximize the log likelihood of the correct sequence for a given sequence for the entire training data.
The gradient of L(θ) is as follows: One drawback of MLE is the exposure bias (Ranzato et al., 2015). The decoder predicts a word conditioned on the correct word sequence (y t−1 1 ) during training, whereas it does with the predicted word sequence (ŷ t−1 1 ) at test time. Namely, the model is not exposed to the predicted words in training time. This is problematic, because once the model fails to predict a correct word at test time, it falls off the right track and does not come back to it easily. Furthermore, in most sentence generation tasks, the MLE objective does not necessarily correlate with our final evaluation metrics, such as BLEU (Papineni et al., 2002) in machine translation and ROUGE (Lin, 2004) in summarization. This is because MLE optimizes word level predictions at each time step instead of evaluating sentences as a whole.
GEC is no exception. It depends on sentencelevel evaluation that considers grammaticality and fluency. For this purpose, it is natural to use GLEU (Napoles et al., 2015), which has been used as a fluency-oriented GEC metric. We explain more details of this metric in §2.3.

Neural Reinforcement Learning
To address the issues in MLE, we directly optimize the neural encoder-decoder model toward our final objective for GEC using reinforcement learning. In reinforcement learning, agents aim to maximize expected rewards by taking actions and updating the policy under a given state. In the neural encoder-decoder model, we treat the encoderdecoder as an agent which predicts a word from a fixed vocabulary at each time step (the action), given the hidden states of the neural encoderdecoder representation. The key difference from MLE is that the reward is not restricted to tokenlevel accuracy. Namely, any arbitrary metric is applicable as the reward. 1 Since we use GLEU as the final evaluation metric, the objective of NRL is to maximize the expected GLEU by learning the model parameter.
where S(x) is a sampling function that produces k samplesŷ 1 , ...ŷ k , p(ŷ|x; θ) is a probability of the output sentence, and r(ŷ, y) is the reward forŷ k given a reference set y. As described in Algorithm 1, given a pair of source sentence and the reference (x, y), NRL takes k sample outputsŷ 1 , ...ŷ k and their probabilities p(ŷ 1 ), ... p(ŷ k ) (line 3). 2 Then, the expected reward is computed by multiplying the probability and metric score for each samplê y i (line 7).
In the encoder-decoder model, the parameters θ are updated through back-propagation and the number of parameter updates is determined by the partial derivative of J(θ), called the policy gradient (Williams, 1992;Sutton et al., 1999) in reinforcement learning: where α is a learning rate and b is an arbitrary baseline reward to reduce the variance. The sample mean reward is often used for b (Williams, 1992), and we follow it in NRL.
It is reasonable to compare NRL to minimum risk training (MRT) (Shen et al., 2016). In fact, NRL with a negative expected reward can be regarded as MRT. The gradient of MRT objective is a special case of policy gradient in NRL. We show mathematical details about the relevance between NRL and MRT in the supplemental material (Appendix A).

Reward in Grammatical Error Correction
To capture fluency as well as grammaticality in evaluation on such references, we use GLEU as the reward. We have shown GLEU to be more strongly preferred than other GEC metrics by native speakers (Sakaguchi et al., 2016). Similar to BLEU in machine translation, GLEU computes n-gram precision between the system hypothesis (H) and the reference (R). In GLEU, however, ngrams in source (S) are also considered. The precision is penalized when the n-gram in H overlaps with the source and not with the reference.
is the number of overlapped n-grams among the sets, and BP brevity penalty is compute based on token length in the system hypothesis (h) and the reference (r).

Experiments
Data For training the models (MLE and NRL), we use the following corpora: the NUS Corpus of Learner English (NUCLE) (Dahlmeier et al., 2013), the Cambridge Learner Corpus First Certificate English (FCE) (Yannakoudakis et al., 2011), and the Lang-8 Corpus of learner English (Tajiri et al., 2012). The basic statistics are shown in Table 1. 3 We exclude some unreasonable edits (comments by editors, incomplete sentences such  as URLs, etc.) using regular expressions and setting a maximum token edit distance within 50% of the original length. We also ignore sentences that are longer than 50 tokens or sentences where more than 5% of tokens are out-of-vocabulary (the vocabulary size is 35k). In total, we use 720k pairs of sentences for training (21k from NUCLE, 32k from FCE, and 667k from Lang-8 Hyperparameters For both MLE and NRL, we set the vocabulary size to be 35k for both source and target. Words are represented by a vector with 512 dimensions. Maximum output token length is 50. The size of hidden layer units is 1,000. Gradients are clipped at 1, and beam size during decoding is 5. We regularize the GRU layer with a dropout probability of 0.2. For MLE we use mini-batches of size 40, and the ADAM optimizer with a learning rate of 10 −4 . We train the encoder-decoder with MLE for 900k updates, selecting the best model according to the development set evaluation. For NRL we set the sample size to be 20. We use the SGD optimizer with a learning rate of 10 −4 . For the baseline reward, we use average of sampled reward following Williams (1992). The sentence GLEU score is used as the reward r(ŷ, y). Following a similar (but not the same) strategy of the Mixed Incremental Cross-Entropy Reinforce (MIXER) algorithm (Ranzato et al., 2015), we initialize the model by MLE for 600k updates, followed by another 600k updates using NRL, and select the best model according to the development set evaluation. Our NRL is implemented by extending the Nematus toolkit (Sennrich et al., 2017)  In addition to the automated metric (GLEU), we run a human evaluation using Amazon Mechanical Turk (MTurk). We randomly select 200 sentences each from the dev and test set. For each sentence, two turkers are repeatedly asked to rank five systems randomly selected from all eight: the four baseline models, MLE, NRL, one randomly selected human correction, and the original sentence. We infer the evaluation scores by comparing pairwise rankings with the TrueSkill algorithm (Herbrich et al., 2006;Sakaguchi et al., 2014). 6 The four baselines are not tuned toward the same dev set as MLE and NRL. Also, they use different training set (Table  2). We compare them just for reference.    Results Table 3 shows the human evaluation by TrueSkill and automated metric (GLEU). In both dev and test set, NRL outperforms MLE and other baselines in both the human and automatic evaluations. Human evaluation and GLEU scores correlate highly, corroborating the reliability of GLEU. With respect to inter-annotator agreement, Spearman's rank correlation between Turkers is 55.6 for the dev set and 49.2 for the test set. The correlations are sufficiently high to show the agreement between Turkers, considering the low chance level (i.e., ranking five randomly selected systems consistently between two Turkers). Table 4 and 5 show the M2 (F 0.5 ) scores (Dahlmeier and Ng, 2012), which compute phrase-level edits between the system hypothesis and source and compare them with the oracle edits. Although this metric has several drawbacks such as underestimation of system performance and indiscrimination between "no change" and "wrong edits" (Felice et al., 2014), we see that the correlation between the M2 scores and human evaluation is still high in the result.
Finally, Table 6 shows the percentages of preference in the pairwise comparisons between NRL and MLE. In both the dev and test sets, around 30% of NRL corrections are preferred over MLE and approximately 50% are tied.
Orig. but found that successful people use the people money and use there idea for a way to success . Ref.
But it was found that successful people use other people 's money and use their ideas as a way to success . MLE But found that successful people use the people money and use it for a way to success . NRL But found that successful people use the people 's money and use their idea for a way to success .
Orig. Fish firming uses the lots of special products such as fish meal . Ref.
Fish firming uses a lot of special products such as fish meal . MLE Fish contains a lot of special products such as fish meals . NRL Fish shops use the lots of special products such as fish meal .  Table 7 presents example outputs from MLE and NRL. In the first example, both MLE and NRL successfully corrected the homophone error (there vs. their), but MLE changed the meaning of the original sentence by replacing their idea to it. Meanwhile, NRL made the sentence more grammatical by adding a possessive 's. The second example demonstrates challenging issues for future work in GEC. The correction by MLE looks fairly fluent as well as grammatical, but it is semantically nonsense. The correction by NRL is also fairly fluent and makes sense, but the meaning has been changed too much. For further improvement, better GEC models that are aware of the context or possess world knowledge are needed.

Conclusions
We have presented a neural encoder-decoder model with reinforcement learning for GEC. To alleviate the MLE issues (exposure bias and tokenlevel optimization), NRL learns the policy (model parameters) by directly optimizing toward the final objective by treating the final objective as the reward for the encoder-decoder agent. Using a GEC-specific metric, GLEU, we have demonstrated that NRL outperforms the MLE baseline on the fluency-oriented GEC corpus both in human and automated evaluation metrics. As a supplement, we have explained the relevance between minimum risk training (MRT) and NRL, claiming that MRT is a special case of NRL.

A Minimum Risk Training and Policy Gradient in Reinforcement Learning
We explain the relevance between minimum risk training (MRT) (Shen et al., 2016) and neural reinforcement learning (NRL) for training neural encoder-decoder models. We describe the detailed derivation of gradient in MRT, and show that MRT is a special case of NRL. As introduced in §2, the model takes ungrammatical source sentences x ∈ X as an input, and predicts grammatical and fluent output sentences y ∈ Y . The objective function in NRL and MRT are written as follows.
where r(ŷ, y) is the reward and ∆(ŷ, y) is the risk for an output (ŷ). For the sake of simplicity, we consider expected loss in MRT for a single training pair: q(ŷ|x; θ, α)∆(ŷ, y) where q(ŷ|x; θ, α) = p(ŷ|x; θ) α ŷ ∈S(x) p(ŷ |x; θ) α S(x) is a sampling function that produces k samplesŷ 1 , ...ŷ k , and α is a smoothing parameter for the samples (Och, 2003). Although the direction to optimize (i.e., minimizing or maximizing) is different, we see the similarity between J(θ) and R(θ) in the sense that they both optimize models directly towards evaluation metrics. The partial derivative ofR(θ) with respect to the model parameter θ is derived as follows.


extfieldsofstudy: Biology Medicine

text:
Optimizing DNA assembly based on statistical language modelling

Abstract By successively assembling genetic parts such as BioBrick according to grammatical models, complex genetic constructs composed of dozens of functional blocks can be built. However, usually every category of genetic parts includes a few or many parts. With increasing quantity of genetic parts, the process of assembling more than a few sets of these parts can be expensive, time consuming and error prone. At the last step of assembling it is somewhat difficult to decide which part should be selected. Based on statistical language model, which is a probability distribution P(s) over strings S that attempts to reflect how frequently a string S occurs as a sentence, the most commonly used parts will be selected. Then, a dynamic programming algorithm was designed to figure out the solution of maximum probability. The algorithm optimizes the results of a genetic design based on a grammatical model and finds an optimal solution. In this way, redundant operations can be reduced and the time and cost required for conducting biological experiments can be minimized.

INTRODUCTION
With the development of synthetic biology, it has become necessary to develop tools and methodologies to streamline the design of custom genetic constructs (1). Gene expression studies, gene network studies, protein expression vector design and metabolic engineering are some of applications of this technology (2,3). There are web-based applications such as GenoCAD to fill the needs of these scientific studies. GenoCAD is built upon a solid computational linguistic foundation, and can be used to design synthetic genetic constructs (4). Yet, it captures design strategies of synthetic genetic constructs in the form of grammatical models (5). Promoters, ribosome-binding sites (RBS), genes and termina-tors are all categories of parts that are needed for designing complex genetic constructs (6)(7)(8). Decomposing biological sequences into functional modules as genetic parts is one of the ways to update synthetic biological database (9). There are some assembly standards when assembling these parts into genetic constructs. The BioBrick Foundation (BBF) has been instrumental in promoting the BioBrick standard. A BioBrick compliant part is a DNA fragment flanked by a prefix and a suffix sequence having specific restriction sites (10,11). Two BioBrick parts can be assembled by using a specific series of restriction digestions and ligations independent of the parts sequences. Theoretically, any set of genetic parts compliant with the same standard can be assembled by using specific restriction and ligation enzymes.
When assembling genetic parts into genetic constructs, researchers are often unsure of choosing a part in a particular category. Thus, the molecular biological experiment of assembling is always time-consuming, expensive, and errorprone. In order to reduce the time and cost of assembling, researchers and engineers develop robotic platforms that can help automate the process of assembling many multikilobase genetic constructs. The determination of an optimal assembly process can be totally automated by dynamic programming algorithms, without experiences (12). In other robotic platform, a user can design a synthetic construct by successively selecting design rules to transform the structure of the design. Finally, the user can select specific parts to complete the design (13). However, increasing number of genetic parts is being imported. At the last step of assembling, users are always puzzled in choosing a suitable part from few sets of categories ( Figure 1). The objective of this study was to overcome this difficulty. Here, we introduce statistical language model (SLM), which can help streamline the assembling process. The first goal of SLM is to build a statistical language model that can estimate the distribution of natural language as accurate as possible (14). The original (and is still the most important) application of SLMs is speech recognition, but SLMs also play a vital role in various other natural language applications as diverse as machine translation, part-of-speech tagging, intelligent in- put method and Text To Speech system. The statistical language model in this paper is based on the statistical parameters coming from BioBrick standard parts and widely used plasmids. After transforming the assembling process into the mathematic model, a dynamic programming algorithm can be performed to choose suitable parts composing the final genetic construct. The algorithm takes experience of former iGEM design and some widely used plasmids into account to reduce the cost, time and errors of the assembling process. This method can not only optimize the result of genetic design from other robotic platform but also can help design new projects by considering former experience.

MATERIALS AND METHODS
We use link http://parts.igem.org/das/parts/entry points/ to download the entry points to the parts that we want to analyze in June 2014. The version of this file published at that time included 7242 parts. A Perl script was developed to parse out the content of each part from the link http://parts. igem.org/das/parts/features/?segment=part#. We then decomposed them into structured data format, which could be imported into a MySQL database. After being imported into a MySQL database, 75744 features were parsed out from these parts. The parts include both basic parts (e.g. promoter and RBS) and composed parts, which include multiple basic parts (e.g. device, project and composite). The basic parts include categories of Regulatory, RBS, Coding, Terminator and Plasmid Backbone. We queried the MySQL database to extract the basic parts and counted their usage in composed parts. We also developed Perl script and SQL sentences to analyze composed parts and counted the usage of two (parts pair), three (parts triple), and four (parts quadruple) adjacent basic parts in them. By querying the MySQL database, we extracted a set of 1682 basic parts compliant with RFC 23 standard (15). It means that the sequence of these basic parts does not include any of the restriction sites used by the assembly standard. These 1682 basic parts include 405 promoters, 42 RBSs, 57 terminators and 1178 genes. We used these basic parts to design some genetic constructs. The usage frequencies of basic parts, parts pair, parts triple, and parts quadruple in the dataset were calculated.
We also downloaded genetic parts from GenoLIB database and developed Perl scripts and SQL sentences to analyze them. 1633 parts which consisted of 84 categories were included and their usages in 1750 commonly used plasmids were counted. The usages of parts pair, parts triple and parts quadruple were also counted for optimizing parts assembly based on SLM. Readers can be referred to homepage of GenoCAD (www.genocad.com) for more information of these parts and categories.

Mathematic model
For example, at the last step of GenoCAD design, every icon has its option. It is somewhat difficult for the designer to choose the most suitable part to complete the design (Figure 1). There are too many combinations of parts to form different genetic constructs. It is impossible to exam every combination with wet experiment. And adopting a reasonable mathematical model to depict the genetic construct will facilitate selecting suitable parts (16). To overcome this problem, statistical language model (SLM) is introduced. In this model, whether a sentence (S) is meaningful and reasonable is based on the probability it will occur. A sentence (S) is composed of a sequence of words. Here S is a genetic construct that is made of basic parts, and the words are these basic parts. Now, S = part 1 ,part 2 ,. . . ,part n and we need to know its P(S)--the probability that it will occur. Thus, P(S) = P( par t 1 , par t 2 , ..., par t n ) ( 1 ) According to conditional probability formula P( par t 1 , par t 2 , ... par t n ) = P( par t 1 ) · P( par t 2 | par t 1 ) · P( par t 3 | par t 1 , par t 2 ) · · ·P( par t n | par t 1 , par t 2 , ..., par t n−1 ) In formula (2), P(part 1 ) means that the probability part 1 appears in the design. P(part 2 |part 1 ) denotes the probability that part 2 appears with part 1 prior to it. According to formula (2), the probability part n appears is determined by all the parts that appear prior to it. The P(part 1 ) and P(part 2 |part 1 ) are easy to calculate, but calculating P(part 3 |part 1 ,part 2 ) is difficult. Further, calculating P(part n |part 1 ,part 2 ,. . . ,part n-1 ) is very difficult, because much more variables are involved in it. The conditions are too complex to gauge. We believe, based on Markov Hypothesis, that the probability that a part will occur is only concerned with the part prior to it. Thus, formula (2) can be simplified as: This is the Bigram of statistical language model. However, when assembling genetic parts, whether a gene can be expressed effectively is not only concerned with its RBS but also with its promoter and plasmid backbone. Therefore, we believe that the probability that a part will occur in an S is concerned with the adjacent two or three parts prior to it. Thus, formula (2) can be simplified as: Formula (4) is the 3-gram model of statistical language model. Based on this theory, the 4-gram model can be established. According to conditional probability formula: We use usage frequencies of parts pair, parts triple, and usage frequencies of basic parts to estimate P (part i-2 , part i-1 , part i ), P(part i-2 , part i-1 ) and P(part i ), respectively.

Count(all par ts)
According to formula (5) and the above formulas, In this way, any component in formula (4) can be calculated.
At the last step of design ( Figure 1), there are too many combinations of basic parts to complete the design. Which one is the most reasonable and meaningful? We believe that the part combination with the largest probability of occurrence is the answer. We have all the candidate paths, and a path will result in an S (a path = a S = part 1 ,part 2 ,. . . ,part n ). The best path is represented by PATH.
To avoid memory overflow when performing the algorithm on a computer, we considered the log of P(S).
Based on formula (6), we derived the following formulas

Count(all par ts)
Since we extracted the dataset from a relatively sparse corpus, the zero-frequency problem would arise when parts pair, parts triple never occurred in the training corpus. The zero-frequency problem means when some parts pairs and triples never appear in a corpus, their Count will be zero. Then, according to above formulas the probability they appear is zero. This circumstance will cause troubles in calculating P(S) and selecting the PATH. To overcome this, we use Add-one (Laplace) Smoothing (17). Thus, these formulas should be represented as: In formulas (8) and (9), N is the number of bi-gram (parts pair) and W is the number of 3-gram (parts triple). Formulas (8) and (9) were used to fill the corresponding component in formula (7). Based on same theory, a 4-gram model of statistical language model can be established and corresponding probability can be calculated. The resulted PATH was the S with the largest probability of occurrence in all candidate paths. We used dynamic programming algorithm to figure out the PATH from all candidates. Transform a cistron (Cis) into a rbs (RBS) and a gene (GEN) Cis RBS-GEN 7 Transform a terminator (TERM) into two terminators (TERM)  TERM  TERM-TERM  8 Transform a gene (GEN) into two genes (GEN) GEN GEN-GEN

Algorithm
Next, we need to find a path in the lattice in Figure 1. This path is composed of a series of parts and will be the S with the largest probability. It reflects how formula (7) can be solved. The algorithm of 3-gram model is presented as an example, it originates from the Viterbi algorithm (18) and consists of three steps: Firstly, a candidate lattice was built ( Figure 2). Every icon (category) corresponds to one column, and every node in a column corresponds to a basic part. At the start and end of the lattice, BEG and END columns were added. In these two columns, two virtual nodes of B and E, respectively, were added ( Figure 2). Every node is a triple-tuple < name, V, P >, and the first element name was filled with basic part name.
Secondly, the lattice was filled (Figure 3). In the lattice from left to right, for every node of a triple-tuple < name, V, P >, the V and P are calculated and filled. V was filled with the maximum value selected from combining operation of three nodes in three adjacent columns. P would then store the address of the node prior to it, where V is derived from via combining operation.
(1) First column, for the B node, let V = 0 and P = NULL.
(2) Second column, every node < name, V, P > (name∈{I0500, R0011, . . . , R0040, . . . }) was combined with B node, and its V and P were calculated as: (3) Third column, every node < name, V, P > (name∈{R0032, R0034, . . . , R0041, . . . }) was combined with every node in the second column, and its V and P were calculated as: V = max{log P( par t par t pri or )}, P = addr ess wher e V comes f rom (4) Fourth column, every node < name, V, P > was combined with every node in the previous two columns, and its V and P were calculated as:  (5) Step 4 was repeated; every node in the current column was combined with every node in the previous two columns, and its V and P were calculated.
(6) In the END column, V is the maximum value selected from the nodes in the previous column, P would store the address of the node where V is derived form.
Thirdly, the PATH was recalled and obtained ( Figure  4). Starting from node E, the P prior to it was continually searched (Figure 4). Finally, the PATH with the largest probability was found, and the resulted S was the genetic construct that was designed. In same way, a dynamic programming algorithm can be implemented in a 4-gram model and the corresponding PATH can be figured out. If the length of S is L, and the maximum node number in a column is D, the algorithm complexity of this algorithm in a 3-gram model will be O(L·D 3

RESULTS
The general methodology of developing grammars to model the structure of synthetic genetic constructs has been previously described in details (4,19). The basic grammar is clear: PRO (promoter)-RBS (ribosome-binding sites)-GEN (genes)-TERM (terminator). The grammatical model used in this study is similar to the context-free grammar (CFG) (19), but has new rewriting rules to allow protein fusion. The full grammatical model is described in Table 1. We also used GenoLIB grammar to design new genetic constructs, the database and the grammar also have been described before in details (9).
To demonstrate how to assemble BioBrick parts to form a functional biosynthetic system, we selected the banana odor biosynthetic system (http://parts.igem.org/ Part:BBa J45900), designed and implemented by the MIT iGEM team in 2006. The system contains two expression cassettes: one with BAT2 and THI3 genes, which produces isoamyl alcohol; and the other catalyzes the conversion of the cellular metabolite leucine to isoamyl acetate or banana odor. We can design the system according to the grammatical model.   This is the actual part that banana odor biosynthetic system consists of.
For another example, we selected the wintergreen odor biosynthetic system (http://parts.igem.org/Part: BBa J45700), also designed and implemented by the MIT iGEM team in 2006. The system consists of two expression cassettes: one produces salicylate acid from the cellular e182 Nucleic Acids Research, 2017, Vol. 45, No. 22 PAGE 6 OF 9 The 4-gram model recommended: Two examples repeated the combination R0040-B0030. According to expertise in this field, R0040-B0030 together with Biobrick scars at each junction would result in a 93bp direct repeat, which might be expected to make the system unstable. To avoid this bias, we modified the parameters by deleting combinations with less usage frequency (less than four times in parts usage, less than three times in parts pair usage, less than three times in parts triple usage). This is a general procedure to correct some deviations in assembling results. Then, in the first example the assembling algorithm of 3-gram model recommended: The 4-gram model algorithm also recommended: In the second example the 3-gram model recommended: The 4-gram model recommended: And this is the actual part that wintergreen odor biosynthetic system consists of.
The third example, we used the sascsc design in Public Designs of GenoCAD ( Figure 5). This design used Geno-LIB v10 grammar and included All Parts. When inputting the design PRO RBS CDS ETER SPCR ENH VREP ENH, the assembling algorithm of 3-gram model recommended: In the first example, the 4-gram model recommended the same assembly to the original. The 3-gram model recommended assembly different from the original. In the second example, the 4-gram model recommended an assembly similar to the original composition. The 3-gram model recommended assembly quite different from the original. After modifying the parameters, in both examples the 3gram model recommended an assembly similar to the original and the 4-gram model recommended the same one to the original. Experienced users can modify the parameters to optimize assembling results. In the first example that simulating iGEM design in Supplementary Data, both 3 and 4-gram model recommended assemblies different from the originals. After modifying the parameters, the 4-gram model recommended a same one to the original. When we develop more complicated designs (the other three examples simulating iGEM design), the algorithm recommended quite different results (Supplementary Data). One reason is the corpus is fairly sparse, more successful assemblies are needed to enrich the corpus. And the other important reason is that when the designs become complicated a more advanced grammar will be needed. We use GenoLIB v10 grammar in GenoCAD to the third and fourth examples, and the third one is also a public design. The algorithm recommended some assembly results for consideration. If we need some other options, we can exclude some parts and repeat the algorithm. It will recommend some other optimized assemblies for consideration. If we have known that some parts are definitely connected, we can determine them first (or evaluate them higher) then implement the algorithm. Readers can be referred to Supplementary Data for these applications and more examples. Theoretically, the 4gram model will recommend a more reasonable assembly result than 3 and Bi-gram model. But we think in some cases it must be tested by a wet experiment. The algorithm can be iterated to yield different optimized results for consideration. If we develop new project according to a grammar and carry out the algorithm at the last step, the algorithm will yield an optimized assembly based on experience. Students enrolled in the iGEM competition may be an important group of potential user of this method, and the Bio-Brick grammar has been developed with this group in mind.

DISCUSSION
This paper presents a statistical language model for synthetic biological parts assembling. After converting syn-e182 Nucleic Acids Research, 2017, Vol. 45, No. 22 PAGE 8 OF 9 thetic biological parts assembly process into a 3-or 4-gram model, a dynamic programming algorithm was carried out to select an optimized result. The method can not only be applied to optimize the assembly of a design in a synthetic biological robotic platform such as GenoCAD, but can also be independently applied to automate the DNA assembly process in synthetic biology. After entering categories of synthetic biological parts according to a grammar, the algorithm automatically selects suitable parts to form a reasonable construct by considering successful experiences. In this way, redundant operations can be reduced, and the time and cost required for conducting biological experiments can be minimized. As described previously, this method is based on 3-or 4-gram model. It indicates every part involved in the assembly process is concerned with the adjacent two or three parts prior to it. But in real world DNA assembly process, for an example, whether a gene can be expressed effectively is not only related to its promoter, RBS but also its plasmids backbone and other regulating sequences. In order to simulate real world assembly process, models higher than 4-gram should be introduced. These models indicate every part involved in the assembly process is concerned with more than three parts prior to it. But in these higher-gram models the conditional probability is very difficult to calculate. When N = 5 or more, though the accuracy in other natural language applications such as machine translation, part-of-speech tagging, intelligent input method will increase significantly, powerful computer will be needed (14).
When calculating the conditional probability, we used Add-one (Laplace) smoothing to overcome zero-frequency problem. However, it is always not a good choice and the disadvantages of Add-one (Laplace) smoothing are wellknown: it allows considerable amount of the probability space to unseen events, and is poor at predicting the actual probabilities of bi-grams (17). It was used just for simplicity, considering that any two parts compliant with the same standard can be connected. We intend to develop 5-or more-gram models, and expand the corpus to simulate the assembly process more reasonably. Other smoothing technologies such as Good-Turing Smoothing, Katz backoff, Interpolation Smoothing (20,21) will be considered to improve the mathematical model. Some parts are overwhelmingly likely to be returned in any analysis. One of the reasons is that 'noises' in the corpus cause results deviating, and we can delete these 'noises' to correct the deviation. We employed commonly used combinations with higher usage frequency (more than three times in parts usage, more than two times in parts pair and triple usage, and all the parts quadruple) in the iGEM dataset, and we defined these combinations were 'successful' or 'good' words and the others was useless 'noises'. We downloaded a relatively sparse corpus from the iGEM website, and derived a fairly sparse corpus from widely used plasmids. We also counted the usage of parts and two or more continuous adjacent parts. When developing new projects, some parts pairs, parts triples and parts quadruples never occur in the sparse corpus. These circumstances always raise the zerofrequency problem, and cause optimized results deviating. Besides improving smoothing technology, expanding the corpus is absolutely necessary. But expanding corpus needs describing the nature of features and parts in a unified way. In other words, same sequence should have same name and same description. This is still a more difficult issue. This can be solved by the development of an ontology giving the community a common controlled vocabulary to describe the features. And developing the Synthetic Biology Open Language will promote this process.
Based on previously described linguistic models of synthetic DNA sequences, the paper presents a computational supplement for the AutoCAD platform of Synthetic Biology. It also has raised an important question of a too wide choice being offered at the final stage of the design. It is fairly important to take into account success of the previ-PAGE 9 OF 9 Nucleic Acids Research, 2017, Vol. 45, No. 22 e182 ous assemblies when creating a new design. For an inexperienced user or a new person to Synthetic Biology, it will be difficult to make a right choice of parts to be used in the assembly. The algorithm help users by suggesting the most common combinations of parts based on a body of previously analyzed and successful constructs. Besides optimizing BioBrick parts assembling, by using GenoLIB grammar and dataset in GenoCAD to create designs and optimize the assembly it demonstrates that the method can be used more practically and universally. The newly developed feature will facilitate popularizing of Synthetic Biology to a wider community and might help to erase inconsistency and jargon used in this field. On the other hand, when collecting data from previous assemblies we know usage frequencies of parts and parts connections. This will enrich our knowledge of synthetic biological assemblies and favor the data-driven feature of biotechnology. Next step, more successful assemblies will be taken into account and the algorithm will be improved to enable it useful for a wider scientific community.

SUPPLEMENTARY DATA
Supplementary Data are available at NAR Online.


extfieldsofstudy:
Computer Science
Physics

text:
Information diffusion in interconnected heterogeneous networks

In this paper, we are interested in modeling the diffusion of information in a multilayer network using thermodynamic diffusion approach. State of each agent is viewed as a topic mixture represented by a distribution over multiple topics. We have observed and learned diffusion-related thermodynamical patterns in the training data set, and we have used the estimated diffusion structure to predict the future states of the agents. A priori knowledge of a fraction of the state of all agents changes the problem to be a Kalman predictor problem that refines the predicted system state using the error in estimation of the agents. A real world Twitter data set is then used to evaluate and validate our information diffusion model.

INTRODUCTION
Different topics are discussed/diffused in social networks and because of the distinct dynamics of these diffusions, agents in the social networks are affected in different extents. The temporal and spatial dynamics of diffusion have been studied through sequences of activation nodes and observed as spreading cascades in a network [1].
The information diffusion process models can be classified into three major groups, probabilistic models, thermodynamic models, and counting models. NETINF [2], NE-TRATE [3] and INFOPATH [4] are the probabilistic models which infer the underlying diffusion network among information sources using consecutive hit times of the nodes by a specific cascade. The main idea behind the thermodynamic models [5,6,7,8] is that heat will propagate from a warmer region to a colder region or gas will move from the region with higher density to the region with lower density. Modeling the information as heat or gas, we can write the rate at which information is changing in agent i as: dft' = D Lj A(i, j)(' I/Jj -' I/Ji )-Where ' 1/J; (t) is the state of the i th agent at time t, D is the diffusion constant which reflects the amount of information passing from an agent to another agent in a small interval of time, and A( i, j) is the i, j element of adjacency matrix. The counting models [9] form counting processes to find the number of nodes in each group of susceptible or infected nodes. SIS [ 10] and SIR [ 11] models are two of the well-known ones in this group.
One central challenge in modeling information diffusion is to understand the structure of the cascades; the existence of unknown external influence factors and unclear graph connections obscures this query. In this paper, we have for the first time modeled the simple diffusion on a general multilayer network and applied the model to publication networks and social media data.
The multilayer network connectivity structure has been proposed and studied in [12,13,14,15,16], in particular, a two-layer network has been studied in [7] under the Laplacian dynamics. However, the information flow following a Laplacian process on a multilayer network in its most general form has yet to be studied. A multilayer network (illustrated in Fig. I) takes into consideration additional connection possibilities when the true connections for the agents are uncertain. For example, social media such as biogs consist of a set of documents generated by bloggers over time; these documents may share some topical similarities in spite of the different sources they are generated from. It is possible to structure the document similarities into the relational property as a network of documents. Then one can further associate this layer of connection with the connection of bloggers ( e.g., according to following-follower connection). This leads to a multilayer network model where information diffuse both within a single layer and across the inter-layers. The additional paths due to the multilayer structure will diffuse the information at a secondary degree, specifically, an absence of a direct connection between two bloggers may be reestablished by counting the topical similarities between the documents they are associated with. We will refer to the resulting network from a multilayer construction as an interconnected network of heterogeneous nodes.
In a community-like network setting with common interest, such as a network of professors with their publications, online forum community, we have observed diffusion related thermodynamical patterns. It turns out that the simple diffusion model on the interconnected network structure is very effective in predicting the future state of the agents.  The paper is organized as follows: We propose our new approach in Section 2, and present substantiating experimental results in Section 3. We finally provide the concluding remarks in Section 4.

THE PROPOSED METHOD
In closed systems, all changes in the states of agents are a result of interaction of the agents in the network. In a single layer network, a diffusion process based on heat equation has been studied in [5 , 6, 7, 8). Independent of the nodes in a multilayer network being agents or documents, we generalize the single layer diffusion process to: dX -= -.C.X. dt (I) Where X is a N x T matrix, N being the number of nodes in the multilayer network, and each row of X is storing a Tdimensional state vector for each node . .C. is a N x N supra-Laplacian matrix defined in proposition(!).

Proposition 1
We can generally write the supra-Laplacian matrix of an M layer multiplex network with N nodes in each layer as Eqn. (2). Where .C.L is the supra-Laplacian matrix of the intra-layer connectivity and .C. 1 is the supra-Laplacian matrix of the inter-layer connectivity. .C.L may be in turn, written as direct sum of the Laplacian matrices of the independent intra-layer connectivities: Proof of proposition (1) can be found in the extended version of the paper [17].
Much of the existing work in information diffusion models have a limited scope (of agents, documents, parameters) when predicting the future state of the nodes. More specifically, agent states may be varied by external sources which are not captured in the network, or by some agent actions which may even to some extent, conflict with the model prediction.
Considering an interconnected network with supra-Laplacian matrix .C., to address this additional auxiliary input, we are further generalizing Eqn. (I) to an open system model as follows: vectors with components as independent standard Brownian motions of variances u i and :E is N x T matrix, and each row shows the u i vector for agent i. Inspired by the Ornstein-Uhlenbeck (0.U.) process [18], Eqn. (6) describes the velocity of the topical-state of the nodes as a Brownian motion in presence of friction. In other words, to describe the uncertainty due to external effects, we proceed to view the whole system as a massive Brownian particle. The drift term (first term in right-hand side of Eqn. (6)), however, moves the velocity from a martingale state of u idB( t) towards a consensus (captured by the drift term). Solution of the differential equation in Eqn. (6), can be expressed as: given the states of nodes at time t 0 we can predict the states at time t 1 , t 1 > t 0 as follows: Where e.C(s-t, +to) is a matrix exponential and itself is a N x N matrix.
Our proposed learning procedure will evaluate the diffusion constants in the supra-Laplacian matrix C as well as the :E matrix. To that end, we proceed to minimize the Frobenius norm of the difference between X and it's predict X, resulting from, Solving this optimization problem helps us decompose the predicted matrix into two main components on the right-hand side of Eqn. (7), the first term representing the interactions in the network, while the second quantifying the uncertainty which results from auxiliary inputs into the system.

Diffusion Network Estimation (Leaming the Supra-Laplacian Matrix)
The supra-Laplacian matrix C which we use in Eqn. (6) for state prediction, is a result of the network connectivity (refer to Eqn. (2)). In practice, hidden connections are pervasive, introducing uncertainty in the prediction, which are causing the information diffusion to require more than the predefined, explicit connections from the network. To that end, consider observations ofX(t) overt E [O, t 1 J, denote x(t) := vec(X(t)), the vectorization of X(t) to obtain a vector differential system in order to learn the supra-Laplacian matrix C of Eqn. We consider the simple cost function J = !t:r E, where E = x -i, and hence for the estimation A we have A = ' Y (x -i)xr (derivative of J with respect to x) , where the estimation i(t + 1) = cAx(t) , and~/ > 0 is chosen appropriately as the scaling gain. In optimization iterations, the estimated value of A at ith iteration is as follows: We use A. 0 =Ir @ (-C), the graph Laplacian of the explicit following-follower network (as initialization). The learned A may, however, not be exactly structured as Ir @ (-C), due to dependence of topics in the state space, as well as the nonlinearity and non-homogeneity of the diffusion. The resulting error E shall be considered for the estimation of the noise in the Kalman-Bucy filter as discussed next.

A Refined Prediction: Kalman-Bucy Filtering
In prediction applications, the actual states of some of the nodes are sometimes known, and we want to predict those of all remaining nodes. An example of this may be seen in social networks, where state of the hub nodes, such as famous people or users with less restrictive privacy policies are known to the public, and one is interested in predicting the state of other less accessible users. Having partial knowledge of the states of a fraction of the nodes in the network, changes the state prediction problem to a Kalman predictor problem, and helps to refine the predicted states using a Kalman filter. We propose a Kalman-Bucy filter as the optimal linear predictor for our system, and we write the observation equation as y(t) = (Ir @H)x(t) +v(t), with Has a diagonal indicator matrix with 1 in all the observed entries, and O in all other entries. A having been learned (see above Section), Kalamn-Bucy equations may be written as: (10) where 1l = Ir @ Hand the noises w(t) and v(t) are zeromean white (temporally) processes, i.e, E(w(t)w(sf) = By considering small time intervals on discretization of the linear continues time system ( c5t = 1 ), one can write the state equation as x(t + 1) = Fx(t) + w(t), where F =I+ A.
Having Eqn. (10) and x(t + 1) = Fx(t) + w(t) as the state and observation equations respectively, we can predict and refine the predicted states of the nodes using Algorithm ( 1 ). The "learning phase" of the Algorithm (1) is estimating the supra-Laplacian matrix A (see above Section). The second phase of the algorithm, is refining the estimated state of the nodes. Note that Rt is the covariance of the observational error, and Xt 2 1t, denotes the linear prediction of x at time t 2 given observations up to and including time t 1 • The state covariance Ilt satisfies the Riccati equation: • A
The designed algorithm shows the discrete time, state update of the Kalman predictor. The estimated states of the available nodes, 1li(t), are compared with the state of the available nodes, y(t) , as measurements observed over time, to evaluate the extent of statistical noise and other inaccuracies in predicting phase. Fig. (2a) shows the prediction based on a network of 79 professors. A three-layer network is formed with the first layer showing if the two professors have ever published in the same venue or not. The second layer being the research group membership of these professors and the third layer showing the similarity network between the papers published by these professors (extracted by LDA [19] topic modeling of the abstract of the papers with dimension I 0). State of the agents are the I 0-dimensional topical vectors which are the mean of the topical representation of the documents produced by the agents . Over time more documents are getting added and the topical state of the agent are changing. The error measure used in all the experiments is the Frobenius norm of the difference of the estimated state of the nodes and ground truth state of the nodes normalized by the Frobenius norm of the ground truth matrix. As may be seen in Fig. (2a), the prediction method based on a three-layer network achieves a lower error than the prediction based on a single-layer network. Note, the single-layer network does not help in predicting the topical states of the agents. The reason is that there are only 79 agents in this experiment and the co-authorship network between the agents is not particularly suited to predict the future state of the agents. Fig. (2b) is an experiment based on 5000 Twitter users. The first layer is a network among users and the second layer is a network between eight Hashtags used in June 2009. The Hashtags are as follows: #jobs, #spymaster, #neda, #l40mafia, #tcot, #musicmonday, #lranelection, #iremember showing how much these Hashtags are similar to each other by counting and normalizing the number of times they have appeared in the same tweet. The average prediction improvement achieved by the two-layer network is about 13 percent. The prediction by first estimating the Laplacian matrix, has about 15 percent improvement over the single layer prediction method. agents in the network respectively. As may be seen in the figures , the prediction error based on the estimated Laplacian matrix yields a lower error than fully trusting the connectivity structure in the network. This as expected, is due to static connectivity network (usually demonstrates the physical or online relation among the agents), falling short on affecting the actual underlying diffusion structure on the network. Having a prior partial knowledge of the agents enabled us to use a Kalman predictor to further refine our prediction.

CONCLUSIONS
In this paper, we proposed a signal processing technique to model and predict states in a multilayer network. The actual diffusion network has been learned by looking at previous diffusion data and has been applied to predicting the future states of agents in the network. Having partial observation of the state of the agents changes the state-space dynamics model to a Kalman filter problem. The Kalman filter allows us to fur-ther refine our state prediction by learning over the prediction error of the observed subset. In future work, we will explore the information diffusion problem with a goal to develop necessary tools to analyze diffusion in more complex network structures.