Deriving Transfer Rules from Dominance-Preserving Alignments

1 Introduction Automatic acquisition of translation rules from parallel sentence-Migned text takes a variety of forms. Some machine translation (MT) svstems treat aligned sentences as unstructured word sequences. Other systems, including our own ((Gr-ishman, 1994) and (Meyers et al., 1996)), syntactically analyze sentences (parse) before acquiring transfer rules (cf. This has the advantage of acquiring structurM as well as lexical correspondences. A syntactically analyzed, aligned cor~ pus may serve ~s an example base for a form of example-based NIT (cf. an efficient algorithm for aligning a pair of source/target language parse trees; ~nd (2) a procedure for deriving transfer rules from this alignment. Each transfer rule consists of a pair of tree fragments derived bv "cutting up" the source and target trees. A set of transfer rules whose left-hand sides match a source language parse tree is used to generate a target language parse tree from their set of right-hand sides, which is a transla.-tion of the source tree. This technique resembles work on MT using synchronous Tree-Adjoining Grammars (cf. (Abeille et al., 1990)). The Proteus translation system learns transfer rules from pairs of aligned source and target reg-ularized parses, Proteus's representation of predicate argument structure(cf. Figure 1)? Then it uses these transfer rules to map source lan-L We thank Cristina Olmeda Moreno for work on parsing our Spanish text. 2Regularized parses (henceforth, "pmse trees") are like F-structures of Lexical }"tmctiou Grammar (LEG), except, that a depenclency st.ruct.ure is used." guage regularized parses generated by ou r source language parser into target language regularized parses. Finally a generator converts target reg-ularized parses into target language sentences. All Mignment f is a I-to-1 partial mapping from source nodes to target nodes. We consider only alignments which preserve the dominance relationship: If node a dominates node b in the source tree. then f(a) dominates f(b) in the target tree. In Figure 1. source nodes ,4. B, C and D map to the corresponding target nodes, marked with a prime, e.g., f(A) = A'. The alignment)nay be represented by the setsign a score to each Mignment f, based on the (weighted) number of pairs in f; finding the best alignment translates into finding the alignment with the highest score. Our algorithms are based on (Farach et al., 199.5) and related work. We needed efficient alignment algorithms because: (1) Corpus-based training requires processing a lot of text; and (2) An exhaustive search of all …

Introduction
Automatic acquisition of translation rules from parallel sentence-aligned text takes a variety of forms. Some machine translation (MT) systems treat aligned sentences as unstructured word sequences. Other systems, including our own ((Grishman, 1994) and (Meyers et al., 1996)), syntactically analyze sentences (parse) before acquiring transfer rules (cf. (Kaji et hi., 1992), (Matsumoto et hi., 1993), and (Kitamura and Matsumoto, 1995)). This has the advantage of acquiring structural as well as lexical correspondences. A syntactically analyzed, aligned corpus may serve as an example base for a form of example-based NIT (cf. (Sato and Nagao, 1990), (l(aji et al., 1992), and (Furuse and Iida. 1994)).
This paper 1 describes: (1) an efficient algorithm for aligning a pair of source/target language parse trees; and (9) a procedure for deriving transfer rules from this alignment. Each transfer rule consists of a pair of tree fragments derived by "cutting up" the source and target trees. A set of transfer rules whose left-hand sides match a source language parse tree is used to generate a target language parse tree from their set of right-hand sides, which is a translation of the source tree. This technique resembles work on NIT using synchronous Tree-Adjoining Grammars (cf. (Abeille et al.. 1990)). The Proteus translation system learns transfer rules from pairs of aligned source and target regularized parses, Proteus's representation of predicate argument structure (cf. Figure 1). 2 Then it uses these transfer rules to map source tan-guage regularized parses generated by our source language parser into target language regularized parses. Finally a generator converts target regularized parses into target language sentences.
An alignment f is a 1-to-1 partial mapping from source nodes to target nodes. We consider only alignments which preserve the dominance relationship: If node a dominates node b in the source tree, then f(a) dominates f(b) in the target tree. In Figure 1. source nodes .4. B, C and D map to the corresponding target nodes, marked with a prime, e.g., f(A) = A'. The alignment may be represented by the set {(d, A'), (B, B'), (C, C'), (D, D')}. We can assign a score to each alignment f, based on the (weighted) number of pairs in f; finding the best alignment translates into finding the alignment with the highest score. Our algorithms are based on (Farach et al., 1995) and related work.
We needed efficient alignment algorithms because: (1) Corpus-based training requires processing a lot of text; and (2) An exhaustive search of all alignments is too computationally expensive for realistically sized parse trees.
Eliminating dominance violations greatly reduced our search space. Similar work (e.g., (Matsumoto et hi., 1993)) considers all possible matches. Although. our system cannot account for actual dominance violations in a given bitext, there are no such violations in our corpus and many hypothetical cases can be avoided by adopting the appropriate grammar. Cases of adjuncts aligning with heads and vice versa are not dominance violations if we replace our dependency analysis with one in which internal nodes have category labels and the head constituents are marked by HEAD arcs and we assume the following Categorial Grammar (CG) style analyses. Suppose that verb (Vi) maps to adverb (A'I) and adverb (A2) maps to verb (V'2), where  We are willing to pay a small penalty to collapse the path from D to E, and align the resulting structure. This leads to new algorithms where the LeA-preserving restriction is replaced by the weaker, dominance-preserving constraint. The rationale behind allowing an edge, say (v, u) to be collapsed when matching two nodes v and v ~, is that we may find some children of u which correspond well to some children [nitially, we fill the matrix S with undefined values, and invoke the procedure SCOREdom, described below, to compute S(root(T), root(T')), the score for matching the root nodes of the trees. During the computation of the score for the roots, the procedure recursively finds the best-scoring matches for all the nodes in the trees. This yields the best alignment of the entire trees.
Table l(a) shows the values of S for the trees in Figure 1. Whenever we compute a score fox" internal nodes, we also record the best way of pairing up their children in Table l That is, the number of rows in M is one more than the number of children of v, and the number of columns is one more than number of children of v ¢. V~re label row d(v) + 1 and column d(v ~) + 1 with a "*". Fill the matrix M: compute the corresponding entry in Mij: The are filled in as in Table 2. The proper values for the parameter functions used above, such as the penalty function Pen and the translation ineasures, are chosen empirically, and constitute the tunable parameters of the procedure. Normally, we will expect that the values of Lexr, ode will be much larger than the values of Lex~rc and Pen.
In the example we used the following settings:

PEEP (i,j)EP
Here P is a legitimate pairing of v and its children against v' and its children. A legitimate pairing P is a set of elements of the matrix M. that conform to the following conditions: 1. each row and each column of M may contribute at most one element to P, except that the row and the column labeled * may contribute more than one element to P 2. if P contains an element Mij corresponding to the node pair (w. w'), and some child node u appears in the Children-Pairing for (w, w'), then the row or column of u may not contribute any elements to P.
We use/.7 ) = £7)(v. v') to denote the set of all legitimate pairings. There are O(d!) such pairings, where d is the greater of the degrees of u and v'. The summation in (l) ranges over all the pairs (i, j) that appear in a legitimate pairing P E /.7)(v, v'). We evaluate this summation for all O(d!) legitimate pairings in/.7), and then select the pairing Pbe~t with the maximum score. Pbest is then stored in the Children-Pairing matrix entry for (v, v'). Table 2       The greedy algorithm aligns trees with n nodes and maximal degree d in O(n2d 2) time.

Acquiring Transfer Rules
This section describes the procedure for deriving transfer rules from aligned parse trees.
First, the best-scoring alignment is recovered from the Children-Pairing matrix, (Table t(b)). 4 Start by including the root node-pair in the alignment, (here (D, DI)). Then, for each pair (v, v ~) already in the alignment, repeat the following steps, until no more pairs can be added to the alignment: (t) look up the Children:Pairing for (v.v The transfer rules derived from Figure t may be written as follows: 1. < root : Excel > --+ < root : Excel > 2. < root : valores > ~ < root : values > 3. < root : libro,subj : xl,a :< root : calcular,obj : x2,en : x3 > > < root : recalculate;subj : Tr(xl),obj : Tr(x2), in : Tr(x3) > Each substructure is represented as a list con-taining a root lexical item, and a set of arcvalue pairs. An arc (role) al with head (value) h is written as al : h, where h is a fixed label (word), a substructure or a variable. If the source substructure has n of the leaves labeled with variables xl, • •., x~, the target will have n of the leaves labeled with Tr(xl),..., Tr(x~), where Tr(x) is the texical translation function. This general structure allows us to capture relations between multi-word expressions in the source and target languages.

Translation
The described procedure for acquisition of transfer rules from corpora is the basis for our translation system. A large collection of transfer rules are collected from a training corpus. When new text is to be translated, it is first parsed. The source tree is matched against the left hand sides of the transfer rules which have been collected. If a set of transfer rules whose left-hand sides match the parse tree is found, the corresponding target structure is generated from the right hand sides of these transfer rules. Typically, several sets of transfer rules meet this criterion. They are ranked by their frequency in the training corpus. Once a target tree has been produced, it is converted to a word sequence by a target language generator. We have applied this approach to the translation of Microsoft Help files in English and Spanish. The sentences are moderately simple and quite parallel in structure, which has made the corpus suitable for our initial system development. To date, we have been using a training corpus of about 1,000 sentences, and a test corpus of about 100 sentences.

Evaluation
Real evaluation of performance of MT systems is time consuming and subjective. Nevertheless, some evaluation system is needed to insure that incremental changes are for the better, or at least, are not detrimental. We measured the success of our translation by how closely we reproduced Microsoft's English (target language) text. Our evaluation procedure computes the ratio between (a) the complement of the intersection set of words in our translation and the actual Microsoft sentence; and (b) the combined lengths of these two sentences. An exact translation gives a score of 0. If the system generates the sentence "A B C D E" and the actual sentence is "A B C F", the score is 3/9 (the length of D E F divided by the combined lengths of A B C D E and A B C F.) The dominancepreserving version of the program produced output for 88 out of 91 test sentences. The average score for these 88 sentences was 0.29:0.21 due to incorrect word matches and 0.08 due to failure to translate because insufficient confidence levels were reached. The LCA-preserving version produced output for only 83 sentences with an average score of over 0.30: about 0.23 due to incorrect word matches and about 0.08 due to insufficient confidence levels. This crude scoring technique suggests that the dominance-preserving algorithm improved our results: more sentences were translated with higher quality. One limitation of this scoring technique is that paraphrases are penalized. An imperfect score (even .20) may signify an adequate translation.


Automatic Bunsetsu Segmentation of Japanese Sentences Using a Classification Tree

Bunsetsu, which is comprised of a content word followed by, possibly 0, function words, is a convenient unit for dependency structure analysis of Japanese. There are, however, no spaces indicating bunsetsu boundaries in the orthographic writing of Japanese. Thus a sentence must be segmented into bunsetsu's by some means prior to dependency structure analysis. Conventionally, such segmentation has been performed by using some kind of hand-crafted rules. This paper describes a novel segmentation method using a classification tree, by which knowledge about bunsetsu boundaries is automatically acquired from a labeled corpus. The method enables quick and easy adaptation to a new task domain, and also to a new system of morpheme categorization without the need of changing the algorithm. Effectiveness of this method is shown through experiments on an ATR corpus and an EDR corpus.

INTRODUCTION
Bunsetsu, which is comprised of a content word with or without being followed by a string of function words, is a convenient unit for dependency structure analysis of Japanese. There are, however, no spaces indicating bunsetsu boundaries in the orthographic writing of Japanese. Thus a sentence must be segmented into bunsetsu's prior to dependency structure analysis. According to the elementary definition of bunsetsu [Nagao, ed. (1984)], such segmentation might look simple. There are, in reality, many factors that complicate the problem. For example, a prefix and/or a suffix can be attached to a content word, and Chinese characters can be concatenated to form a compound word. Some nouns and verbs have functions different from their original ones. Also, there are many idiomatic usages of morpheme concatenations. All these matters cause difficulties in detecting bunsetsu boundaries. Moreover, there is no system of morpheme categorization in Japanese that has received a general consensus. This situation gives rise to another obstacle to establishing a standard method of bunsetsu segmentation.
There have been two major approaches to the bunsetsu segmentation problem: one based on an automaton [Fujio et al. (1997)], or bunsetsu patterns [Kurohashi (1997)] representing a definition of bunsetsu, and the other based on a set of hand-crafted rules [Suzuki (1996)]. In the former approach, one has to give a definition of bunsetsu manually. The latter involves handiwork in getting knowledge about bunsetsu boundaries. Thus both approaches have problems in keeping consistency, coverage and optimality of manually obtained knowledge. When the task domain and/or the system of morpheme categorization are changed, one has to repeat the whole manual process to get new knowledge, which is rather laborious. This paper proposes a method of bunsetsu segmentation using a classification tree [Breiman et al. (1984)], [Quinlan (1993)]., by which knowledge about bunsetsu boundaries is automatically acquired from a corpus. It enables quick adaptation to a new task domain, and also to a new system of morpheme categorization without the need of changing the algorithm. Effectiveness of the method is shown through experiments on an ATR corpus and an EDR corpus.

CLASSIFICATION TREE
A classification tree is a binary tree that classifies objects into classes [Breiman et al. (1984)], [Quinlan (1993)]. Through an automatic generation of a classification tree, one can rapidly acquire underlying regularities in a large amount of data, which are difficult or even impossible for a human to capture by *Department of Computer Science and. Information Mathematics, The University of Electro-Com.munications 1-5-1 Chofugaoka, Chofu, Tokyo, 182-8585 Japan. Email: zhangGachilleus.cs.uec.ac.jp, ozeki©cs.uec.ac.jp intuition. This technique has been well studied in such fields as pattern recognition and machine learning [Safavian et al. (1991)]. A number of applications to natural language processing and speech processing have also been reported [Kuhn et al. (1995)], [Wang et al. (1992)], [Ostendorf et al. (1993)].
The process of classification by a tree is shown in Fig.l. Associated with each non-terminal node of a classification tree is a test. If an object passes a test, it reaches "yes" child-node; otherwise "no" child-node. The process is repeated until the object reaches some terminal node or leaf, which has been assigned to a class label. Only two classes, c1 and c2 , will be considered here. In order to grow a classification tree from the root, objects with class labels, or training objects, are necessary. Also a finite set of tests must be prepared. Suppose that a tree has been grown to some size. It consists of three kinds of nodes: non-terminal nodes, leaves, and active nodes. An active node is a tentative terminal node that will be turned into a non-terminal node or a leaf afterward. Let t be an active node, and L(t) the number of training objects that reach t, among which the number of objects belonging to ci is denoted as Li (t) (i = 1,2). Then the impurity of t, Gini index [Breiman et al. (1984)], is defined as Li(t) L2(t) If the impurity is lower than a prescribed threshold, then t is decided to be a leaf. Otherwise all the tests are tried exhaustively. By means of a test, the training objects that reach t are divided into those that reach the "yes" child-node ty " and those that reach the "no" child-node trio . Let L(tx ) denote the number of training objects that reach tx , where x equals "yes" or "no". Then the test that maximizes the reduction of impurity is selected as the test associated with t, and new active nodes, t y " and trio , are appended under t. If there is no test that reduces the impurity of t, then t is decided to be a leaf. With the root as the initial active node, the above procedure is iterated until all the active nodes are turned into non-terminal nodes or leaves. A leaf t is assigned to class label ci if the majority of training objects that reach t belong to class ci (i = 1, 2).

APPLICATION OF CLASSIFICATION TREES TO BUNSETSU SEGMENTATION
By morphological analysis, a sentence is segmented into morphemes. The attribute values of each morpheme such as the part of speech and the orthographic expression are also obtained. An object to be classified here is a pair of a morpheme sequence derived from a sentence and a boundary between morphemes (a boundary in focus, henceforth): (rn i m2 • • • mn , bi ), where mk (1 < k < n) is a morpheme labeled with its attribute values, and bi the boundary between mi and mi+ i . Therefore a sentence consisting of N morphemes yields N -1 objects. The purpose of classification is to decide whether the boundary in focus is a bunsetsu boundary in the morpheme sequence; this is a classification problem for two classes.
Since it is expected that morphemes near the boundary in focus are important, only two morphemes adjacent to the boundary are tested: one immediately on the left (left morpheme) and the other immediately on the right (right morpheme). Among the attributes of a morpheme, the part of speech is considered to be most important. In some cases, however, the part of speech alone does not provide enough information for bunsetsu boundary detection. Therefore the orthographic expression is employed as another test attribute for some range of morphemes, which are selected by a preliminary experiment. Also the wild card "*" is introduced as a symbol to match any attribute value. Let pi be a part of speech, and W(pi ) the set of orthographic expressions, including "*", of morphemes that belong to pi and are selected by the preliminary experiment. Then the set of the pairs of p i and its orthographic expressions is denoted as {pi } x W(pi ). Let S be the set of all such pairs plus (*, *): Then the set of all the tests is given by S x S in the present work. A. test takes the form < (pi , e l)(P2, *) >, for example. An object will pass this test if the part of speech of the left morpheme equals /31 , its orthographic expression equals e l , and the part of speech of the right morpheme equals /32 . A similar technique has been applied to classification of intonational phrase boundaries [Wang et al. (1992)], though the purpose and the attributes used in their work are quite different from ours.
In the . process of growing a classification tree, an active node t is decided to be a leaf if the condition I(t) < T is satisfied for a prescribed threshold T, or if there is no test that reduces the impurity of t. In this work the value of T was set at 0.1. This condition implies that more than 90% of the training objects that reach t belong to the same class.

EXPERIMENTAL RESULTS
By the procedure described above, classification trees for the bunsetsu segmentation task were generated by using the training objects, and then the results were evaluated. In order to see the influence of different morpheme categorization systems and different sentence materials on the results, two corpora, an ATR corpus and an EDR corpus, were used in the experiments.

Experiment on ATR Corpus
The ATR corpus contains 503 sentences taken from newspapers, magazines, and etc. The sentences are segmented into morphemes, and labeled with the part of speech and the bunsetsu boundary [Abe et al. (1990)]. In this experiment 6994 objects were extracted from the corpus, of which 2000 were used for training, and the remaining 4994 for evaluation. The attribute used for test here was the part of speech only; the orthographic expression was not used. There are 25 parts of speech in the ATR corpus. Fig.2 illustrates a part of the generated tree near the root. The total number of nodes was 69. There was a tendency that the tests related to morphemes with higher frequencies appeared in the nodes closer to the root. Thus it can be said that an efficient order of tests was realized automatically. Table 1 shows the result of evaluation. The symbol Y signifies that the boundary in focus is a bunsetsu boundary, and N signifies that is not. The arrow denotes the classification operation by the tree. So, Y Y means that an object labeled as a bunsetsu boundary in the corpus is classified as a bunsetsu boundary by the tree. The expression IY Y denotes the number of such cases.
About 76% of the errors were of the type Y N. It was found that most of the errors of this type came from concatenations of two common nouns. The generated tree decided a morpheme boundary between common nouns not to be a bunsetsu boundary. However, many of the first common nouns in such concatenations were in fact those that functioned as adverbs, and this kind of objects were labeled as bunsetsu boundaries in the corpus. Thus, the coarseness of sub-categorization of noun was a part of the causes of the errors.

Experiment on EDR Corpus
In the EDR corpus [EDR (1996)], there are no labels indicating bunsetsu boundaries. Instead, it has detailed information about the syntactic structure of sentences. By utilizing this information and the definition of bunsetsu [Nagao, ed. (1984)], 400 sentences were labeled with the bunsetsu boundary. Then 6984 objects for training were extracted from randomly selected 200 sentences, and 7110 objects for evaluation from the rest. The sub-categorization of noun in the EDR corpus seemed too coarse for the present purpose. Therefore it was augmented by using the semantic identifier, which was common to the corpus and the dictionary. The resulting number of parts of speech was 19. In the EDR corpus, sub-categorization of particle is coarser than that in the ATR corpus. Moreover, there is no such category as formal verb, which is employed as a category in the ATR corpus. Therefore, the test of the form <(particle, *), (verb, *)> has little power to distinguish between a bunsetsu boundary and a non bunsetsu boundary; the part of speech information alone, especially for particles and verbs, is not enough for bunsetsu segmentation. For that reason, the orthographic expression was also used as an attribute for test together with the part of speech.
A classification tree with 175 nodes was generated in this case. It was observed that the tree generated on the EDR corpus (EDR tree, henceforth) acquired new segmentation rules that were not acquired in the tree generated on the ATR corpus (ATR tree, henceforth): 1. The boundary between a temporal noun and a common noun was decided to be a bunsetsu boundary, while it was not by the ATR tree. (Because the ATR corpus has no such category as temporal noun, it makes no distinction between a temporal noun and a common noun.) 2. The boundary between an auxiliary verb and a common noun was decided to be a bunsetsu boundary, and a boundary between an auxiliary verb and a formal noun was not, while neither was decided to be a bunsetsu boundary by the ATR tree. (Because the ATR corpus has no such category as formal noun, it makes no distinction between a common noun and a formal noun.) 3. The, boundary between a particle and a common noun was decided to be a bunsetsu boundary, and the boundary between a particle and a formal noun was not, while both were decided to be bunsetsu boundaries by the ATR tree. (The cause is the same as above.) NO <Prefix Common_Noun> yes/ ono INO 4. The boundary between two common nouns was decided to be a bunsetsu boundary, and the boundary between two proper nouns was not, while neither was decided to be a bunsetsu boundary by the ATR tree. (The ATR corpus does not contain enough amount of data for extracting such a segmentation rule.) 5. The EDR tree acquired 12 rules related to symbols, while the ATR tree acquired no such rules.
(The ATR corpus has no occurence of symbols.) Thus, the classification tree extracted the new segmentation rules exploiting the sub-categorization of noun in the EDR corpus. It is observed that in this way a classification tree can adapt to a new system of morpheme categorization. •  Table 2 shows the result of evaluation. The causes of the errors have been analyzed as follows.
• In this experiment, only two morphemes, one on the left and the other on the right of the boundary in focus, were tested. There were, however, some cases where testing more than two morphemes would improve the result.
• The set of orthographic expressions used as attribute values in the tests was incomplete. There were cases where adding some other orthographic expressions would yield better results.
• The training objects did not cover all the linguistic phenomena concerning bunsetsu boundaries. Thus sparseness of the training objects was a problem.
• Some errors obviously resulted from mislabeling in the corpus.

CONCLUSION
The results of this work are summarized as follows: • A classification tree can acquire linguistic knowledge about bunsetsu boundaries automatically, given an appropriately labeled corpus.
• Using the criterion of maximum impurity reduction, it generates efficient rules that capture statistical and logical regularities concerning bunsetsu boundaries.
• It enalbes quick adaptation to a new task domain, and also to a new system of morpheme categorization without the need of changing the algorithm.
Our future work includes: • Improvement of the control method for growing a classification tree by adjusting the threshold value T, or by pruning [Breiman et al. (1984)], [Gelfand et al. (1991)], [Quinlan (1993)], so that a better generalization can be attained.
• Pursuit of a better method for assigning leaves to class labels to enhance the reliability of decision at leaves.
• Automatic acquisition of morphemes whose orthographic expressions are effective in bunsetsu boundary detection.


extfieldsofstudy: Physics Biology

text:
Mapping of mutation-sensitive sites in protein-like chains

In this work we have studied, with the help of a simple on-lattice model, the distribution pattern of sites sensitive to point mutations ('hot' sites) in protein-like chains. It has been found that this pattern depends on the regularity of the matrix that rules the interaction between different kinds of residues. If the interaction matrix is dominated by the hydrophobic effect (Miyazawa Jernigan like matrix), this distribution is very simple - all the 'hot' sites can be found at the positions with maximum number of closest nearest neighbors (bulk). If random or nonlinear corrections are added to such an interaction matrix the distribution pattern changes. The rising of collective effects allows the 'hot' sites to be found in places with smaller number of nearest neighbors (surface) while the general trend of the 'hot' sites to fall into a bulk part of a conformation still holds.

I. INTRODUCTION
In this paper we study how the choice of a particular Hamiltonian is responsible for the distribution pattern of sites sensitive to point mutations in a Heteropolymeric chain.
As shown in [1] using a very simple model [2], in every optimized [3] sequence there are sites at which point mutations are likely to cause misfolding of the native state (we call them 'hot' sites), while there are other sites at which point mutations have no relevant thermodynamic effect ('cold' sites), and we call intermediate sites 'warm'. As known from both experimental [4] and theoretical studies [1] usually proteins are made of few 'hot' sites while the majority of the other sites are 'cold' . Because of the thermodynamic importance of the 'hot' sites it is of general interest to investigate the principles guiding their positioning along the protein chain.
The model used in this work describes the polymer as a chain of beads in a cubic lattice, interacting through the Hamiltonian where B ij is the contact energy between the two residues situated on the i-th and j-th positions, L is the length of the chain and ∆(r i − r j ) has the value 1 if the i-th and j-th are nearest neighbors and zero if not.
In literature, different choices of the matrix B ij have been used. The results of Ref. [1,2] have been found with a matrix [5] whose elements are distributed according to a Gaussian, with average B = 0 and standard deviation σ = 0.3 (in units of kT = 0.6 kcal/mol). With these matrix elements, for every target structure it is possible to select sequences whose native state is unique, stable and kinetically accessible [6]. It has been found that a reliable condition for a site to be 'cold' or 'hot' is intimately connected to the change in the native state energy caused by a point mutation: the bigger is this difference, the more probable for this site to be a 'hot' site. Hot sites of such sequences are mainly in the bulk sites of the native conformation, but can be on the surface as well, while some bulk sites can be rather insensitive to mutations (Fig.1a).
Repeating the same calculations with a random-generated, Gaussian-distributed set of interaction energies, we have observed similar distribution patterns for 'hot' and 'cold' sites ( Fig.1b).
Another choice of the interaction matrix can be made to take into account explicitly the hydrophobic effect encountered in real proteins. The simplest way is to choose the matrix B ij to be composed of only three different elements, namely B HH , B P P and B HP = B P H , where B HH < B P P < B HP . These elements are responsible for the interaction between hydrophobic (H) and polar (P) residues. Unfortunately it was found [2] that for a given target structure and 'HP' interaction matrix it is difficult to construct optimal sequences for which this target structure would be kinetically accessible. As a rule, the optimization of the sequence puts H-residues in the bulk sites (the sites with the greatest number of nearest-neighbors), and every substitution of an H residue with a P residue causes the chain misfolding (See Figs. 2 and 3 in Ref. [7]).
On the way between the random matrix and the highly regular HP interaction model stands the matrix deduces by Miyazawa and Jernigan in [8]. This matrix contains 210 different elements which can still be grouped into 3 big blocks, according to their hydrophobicity.
In this case it is possible to find sequences for which the native state is both stabile and kinetically accessible. It was also found that, as in the situation with only two kinds of residues, 'hot' sites are invariably the sites with the highest number of contacts (bulk sites, The question again is what are the principles guiding the positioning of 'hot' sites along the protein chain and how a particular form of the interaction matrix can influence the distribution pattern of 'hot' and 'cold' mutation sites. This paper is organized as following.
In the next section we will present a convenient representation of an interaction matrix as a function of 'mixing' parameter β. Variation of the 'mixing' parameter will correspond to a change from highly ordered HP like interaction matrix at β = 0 to highly nonlinear matrix at non-zero values of 'mixing' parameter. A distribution pattern of 'cold' and 'hot' sites will be investigated with the use of these interaction matrices. Next we will address the same question by introducing a parameter of 'randomness' γ which would allow us to investigate the mutation sites distribution pattern with highly ordered HP like interaction matrix at γ = 0 and random Gaussian interaction matrix at large γ. Conclusions will be drawn at the end.

II. LTW PARAMETERIZATION
In the work by Lee, Tang and Wingreen [9] a particular interesting parameterization of semi-experimental MJ matrix [8] was introduced, as a consequence of its regularity. In their work it was shown that elements of the MJ interaction matrix can be very nicely fitted as where q α is ascribed to a monomer of kind α and β is a constant. This parameterization involves 20 parameters, instead of 210 parameters of the MJ matrix, each specifying the strength of a particular residue. Using this parameterization we have found that, for the best fit, all q α are negative and range from −2.3 to 0, while β = −0.42. Furthermore, it has been pointed out that the origin of the additive term is due to the hydrophobic effect, while the second order term is responsible for the segregation of dissimilar residues.
Using this parameterization, we can write the Hamiltonian of the chain in a form [10] where n and q have dimensions equal to the number of monomers in the chain. The ith coordinate of n is the number of nearest neighbors for the i-th monomer and the i-th coordinate of q specifies the strength of the residue in the i-th site. C is the contact matrix for a given conformation. In the above reference it has been shown that the Hamiltonian (3) fits very well the original MJ Hamiltonian and, what is more precious, it is very convenient to handle analytically.
One of the problems that can be solved easily using the above Hamiltonian is, given a target structure (C matrix and n) and the composition of the chain in term of residues, to find the sequence which minimize the energy [10]. Particularly, using the fact that the second order term is usually 2−3 times smaller than the first order term, a first order approximation solution can be found minimizing only the solvent exclusion term. The straightforward way is to choose a sequence so that the vectors q and n are as anti-parallel as possible, keeping the constraint of a fixed number of different kinds of monomers. Knowing that all components of q are negative while all components of n are positive, it is necessary to put the residues with the most negative value of q i in the sites of the target structure with the largest number of nearest-neighbors. The effect is, roughly speaking, to put 'hydrophobic' residues (i.e. low q i ) inside the structure while keeping 'hydrophilic' ones (high q i ) on the surface. The second order term in the Hamiltonian (3) is responsible for a fine tuning of residue distribution, mostly inside the hydrophobic/hydrophilic regions, and causes a further decrease of the sequence energy.

III. MUTATIONS AND HOT SITES
According to [1], we label each mutation with the difference of the native state energy of the wild-type sequence and of the mutated sequence where B 0 ij is the interaction element associated with the wild-type sequence and B α ij with a mutated sequence. It has been shown that the information about the thermodynamic features of the mutated sequence is mostly contained in the value of ∆E loc [6], [11].
The energetic effects of mutations in a given site i are studied introducing the average ∆E loc over the 19 possible mutations in this site, For optimized sequences there are few sites (up to 10%) where ∆E loc is large (∼ ∆, where ∆ is the gap between the native state and the random conformations energy [2]), while for the others ∆E loc is much lower. We call the former sites 'hot' and the latter 'cold'. If a mutation occurs in a 'hot' site, there is a high probability that it fills the gap, eliminating the feature of design and causing misfolding of the chain.
For random interaction matrices whose elements have Gaussian distribution, the behavior of hot sites is the same as indicated in Ref. [1]. Hot sites can be both in the bulk and on the surface of the native configuration (See Fig. 1b) with dominance of 'hot' sites in the bulk.
On the other hand, in a model with only two kinds of residues (H and P), the optimization of the sequence puts H residues in the sites with the highest number of nearest neighbors.
In this case (see Ref. [7]), every site containing a H residue is a hot site.
We are now interested in studying the pattern of hot sites in a model where the interaction matrix contains both features of hydrophobic-hydrophilic separation and randomness or complicated non-linearity.

IV. CONSTRUCTION OF THE MAP OF 'HOT' AND 'COLD' SITES
To investigate the behavior of ∆E loc (i) we use the parameterized Hamiltonian (3). It is straightforward to show that, for a wild-type sequence characterized by q where < q > α = 1/20 20 α=1 q α , is the average of the values q α corresponding to the 20 monomers different from the wild-type. With this assumption we have found < q > α ≈ −1.23.
We shell consider first the case β = 0, which is exactly solvable, and then the consequences of the non-linear term introduced via non-zero 'mixing' parameter β..
In the case β = 0 the Hamiltonian contains only the solvent exclusion term H 0 = i q i n i .
As we discussed earlier, optimization of the sequence, given a structure, consists in putting the most hydrophobic residues into the sites with the greatest number of contacts, keeping with the constraint of fixed number of different residues, so that For short chains and 20 letter code used in the model with β = 0 the optimization procedure described above works reasonably good in constructing optimal sequences while for longer chains it seems that the model is not adequate to ensure a single ground state or a ground state well-separated from the other states. Nevertheless, the case β = 0 is a good starting point to investigate the role of the different terms of Hamiltonian (3).
In this case equation (6) can be written as Defining < q >= L i=1 q i / L i=1 n i and substituting (7) in (8) as an approximation for an optimal sequence, we obtain For typical values of < q >∼ −0.6 and < q > α ∼ −1.26 then The shape of this function is plotted in Fig. 2. It is interesting to compare the value ∆E loc (i) for the optimized sequence with the one for a random sequence. We will identify, in the spirit of Random Energy Model [12], 'hot' sites (as defined in Sect. III) with those sites in which the average impact of mutations is greater than for a random sequence. We define a sequence to be random if there is no correlation between the strength q i at a given site, and its number of nearest neighbors n i , so that where q ranges between −2.3 and 0. The values that ∆E rand loc (i) can assume are comprised between the two straight lines plotted in Fig.2a. While the dependence of ∆E loc (i) for the random sequence is linear, for a selected sequence it is quadratic. In the case of the selected sequence the quadratic behavior of the mutation energy versus the number of closest nearest neighbors induces a sharp distinction between bulk sites (n > ∼ 3) and surface sites. As clear form (Fig. 2a), all bulk sites are 'hot', while surface sites are 'cold'. As consequence, 'hot' sites have a certain degree of symmetry in target structures, i.e. no one of the sites with the same number of nearest neighbors is privileged to the others. The map of the 'hot' and 'cold' sites for a Hamiltonian β = 0 and a 36 monomer target structure is presented on (Fig.   1c).
If β is not zero, but still small in absolute values, it is possible to minimize the energy of the sequence in two steps, first minimizing H β=0 = n q and finding an initial trial optimal sequence q tr , and then re-minimizing the same H β=0 with an effective n ef f = n + β 2 q tr C. As was shown in Ref. [10] this procedure is quite reliable for small β.
Using the same approximation (7) as in the previous section for q tr one finds where N i = j C ij n j is the number of nearest neighbors of the nearest neighbors of site i and can assume values in the range {n i , ..., 4n i + 1}. The expression of ∆E β loc (i), then, takes into account, through the value of N i , sites lying further than the nearest neighbors of i.
As consequence of this, we can observe (Fig. 2b) a broadening of the range of values that ∆E β loc (i) can assume for each n i (we will refer to this broadening as 'energy bands' in our further discussion) can be broken thus allowing some hot sites to be found on surface.

C. Explicit Calculations with MJ parameterized Hamiltonian
To investigate how the 'energy bands' depend upon the strength of the nonlinear contribution in the interaction matrix we have made some explicit calculations, using as target structure the 36mers chain displayed on (Fig. 1). We have first calculated the best values of q α and β to fit MJ matrix according to Eq. 2, finding β = −0.42. Using these values for q α , we varied β in the range (−1.5, 1.5), optimizing each time the sequence with a genetic energy minimization technique. The composition has been kept fixed for all values of β and chosen in such a way as to satisfy q i ∼ n i (condition for optimal composition at β = 0). For the sake of computational convenience, the interaction matrix elements have been rescaled to have zero average and standard deviation equal to 1.0. Then, we have plotted the value of ∆E β loc (i) for each lattice site, as function of β. First, we consider the case β < 0. The raising of different 'energy bands' is shown in Fig.3a. For −0.7 < ∼ β < 0 all the bands lay into four distinct groups. The first two groups, which correspond to the sites with n i = 1 or n i = 2, contribute to cold sites. The other two groups correspond to the sites with n i = 3 or n i = 4 defining the 'warm' and 'hot' sites. This situation is very similar to the case of β = 0, where bands do not overlap and 'hot' sites are exclusively in the bulk. It is not surprising to find the same distribution pattern for the MJ matrix (β = −0.42) (Fig.1d).
and HP-like interaction matrix (β = 0) (Fig.1c). For −2.5 < ∼ β < ∼ −1.0 the nonlinear part of the interaction matrix starts playing its role. As was shown in the previous section the second neighbor shell contribute to the value of ∆E β loc (i). At these values of parameter β we observe that some of the energy bands corresponding to 'warm' (n=3) and 'cold' sites (n=1,2) mix, while the bands corresponding to the 'hot' sites stay well separated from the other bands.
In the case of β > 0 (Fig.3b) the non-linear effect is much more dramatic. For β > ∼ 0.2 all bands start mixing allowing 'cold' sites penetrate the bulk while pushing 'hot' sites on a surface. We can rationalise the different pattern of 'energy bands' at β < 0 and β > 0 by examining the Eq.6 and Hamiltonian 3. Noticing that β 2 qC q is of the order of β 2 q n < q > we can rewrite the Hamiltonian 3 in a form where η contains the collective effects and q n(1 + β 2 < q >) describes a 'renormalized' hydrophobic effect. In the case β < 0, ( β 2 < q >) > 0 and the interaction matrix is largely dominated by the hydrophobic effect, while the collective contribution to the Hamiltonian is not strong enough to substantially mix the 'energy bands'.
For the β > 0 case ( β 2 < q >) < 0 and the renormalized hydrophobic effect becomes comparable or smaller than the collective term in the Hamiltonian. This allows all bands to mix substantially.

D. Explicit Calculations for Random Hamiltonian
Another interesting question which can be addressed is how our conclusions are modified by the addition of a random term in the β = 0 Hamiltonian. To study this problem, we have chosen a Hamiltonian in the form where n q comes from the parameterization (2)  In the inserts of Figs.3a,b and Fig.4 shown the energy of the optimal non-mutated sequence for different values of β and γ, respectively. It is possible to observe a sudden decrease in energy of the optimal sequence as β and γ increases signifying that the addition of non-linear terms into a Hamiltonian allows for a much better energy minimization.

V. CONCLUSIONS
In this work we have considered how the regularity of the interaction matrix influence the distribution pattern of 'hot' sites. It has been found that if the matrix is polarized (dominant hydrophobic effect, β ∼ 0 or γ ∼ 0) this distribution is very simple. All the 'hot' sites can be found at the positions with maximum number of closest nearest neighbors (bulk).
With increasing importance of non-linear terms (β = 0,γ = 0) the distribution pattern changes so that the 'hot' and 'warm' sites can be found in places with smaller number of nearest neighbors (surface) while the general trend of the 'hot' sites to fall into a bulk part of a conformation still holds.
As pointed out above this can be rationalized by noticing that if mixing parameter is different than zero each site starts feeling not only its nearest neighbors but also the more distant sites. This leads to a collective nature of the interactions giving rise to a modified distribution pattern of 'hot' sites. Energy of optimal sequence


Robust audio watermarking in the time domain

The audio watermarking method presented below offers copyright protection to an audio signal by modifying its temporal characteristics. The amount of modification embedded is limited by the necessity that the output signal must not be perceptually different from the original one. The watermarking method presented here does not require the original signal for watermark detection. The watermark key is simply a seed known only by the copyright owner. This seed creates the watermark signal to be embedded. Watermark embedding depends also on the audio signal amplitude in a way that minimizes the audibility of the watermark signal. The embedded watermark is robust to MPEG audio coding, filtering, resampling and requantization.

Introduction
The outstanding progress of digital technology has increased the ease with which digital data is reproduced and retransmitted. However, since the advantages of such a progress are broadly available, they oer equally increasing potential to both legal and unauthorized data manipulation. Consequently, the necessity arises for copyright protection of digital products against unauthorized recording attempts, known as data piracy.
Current research in image, audio and video copyright protection exploits the fact that the human visual and audio perception cannot detect slight c hanges in certain temporal or frequency domains of the image and the audio signal, respectively. This property i s c a l l e d masking, according to which a faint but perceptible signal becomes non-perceptible in the presence of another one under certain conditions.
Most research methods consider a watermark signal produced in a unique way b y a function of one or more input keys. These keys can be both owner and signal dependent and generate a signal which i s e m bedded on the original one. The embedding signal is known as a watermark or copyright label. Temporal and frequency characteristics of the original signal should be taken into account i n t h e w atermark casting process to reduce perceptible distortions in the watermarked signal. Each individual that produces or possesses digital data owns a unique key that identies its legal possession and is required for the watermark detection. Besides copyright purposes, a watermark could serve authentication purposes, as well.
Methods that are discussed in this paper investigate the watermarking potential in audio signals, taking into account the specications of the human audio perception. An audio watermark is a perceptually inaudible modication of the audio signal, based on one or more keys determined by the copyright o wner [1]. Whenever a question about ownership arises, keys are used to determine the rightful owner.
Our watermark is embedded in the spatial domain. Unlike other methods, it does not require the original signal for its detection. This way t h e o wner of the data does not have t o k eep double copies of both original and watermarked products.
A watermark has to be statistically undetectable by others to prevent the eorts of its unauthorized removal. This condition is fullled if the potential numberofkeys that produce distinct watermarks is large enough to ensure statistical safety. The detection scheme should be as statistically reliable as possible. False rejection or acceptance of the existence of the watermark should be minimal. Finally, a w atermark has to be robust to signal manipulation and impossible to be removed without signicant alteration of the signal. In other words, a pirate should have to destroy the audio signal before he accomplishes to destroy the watermark. The robustness should extend to common signal processing operations, such as ltering, compression, resampling, requantization, cropping, noise, D/A conversion. Our watermark scheme fullls most of the above conditions up to a satisfactory level and current research is being held out to improve the robustness of the algorithm to any form of unauthorized manipulation.
In the audio watermarking area there are methods that use the frequency domain [1,2]. Some of them exploit the frequency characteristics of the audio signal in order to embed the watermark, by minimizing audible distortions even for high amplitude watermarks. How-ever, most of the above methods require the use of the original signal in order to detect the watermark.
In images, there are methods that cast a watermark either in the spatial [3,4,5] or in the frequency domain [2,6 ]. The casting signal is generated in a random way and digital data is often divided in casting subsets in order to increase the robustness of the detection scheme to signal processing. In both cases, the amplitude of each sample of the watermarking signal is either constant o r calculated as a function of the amplitude of the original sample. Our audio watermarking method has certain similarities with a method used for image watermarking [3].

Watermark Embedding
The watermark embedding scheme proposed in this paper modies original digital audio signals, which are represented as 16-bit or 8-bit sample sequences, by c hanging the least signicant b i t s o f e a c h sample. The result is a s l i g h t amplitude modication of each sample in a way that does not produce any perceptual dierence. Let us assume an audio signal of N samples x(i), i = 1 ; : : : ; N .
In order to embedawatermark we modify each sample using a function f(x(i); w (i)), where w(i) i s t h e w atermark signal in the range [ ; ] and is a constant. The watermarked sample y(i) is therefore: The signal to noise ratio is calculated by S NR= 1 0 log 10 P n x 2 (n) P n [x(n) y(n)] 2 Here, it is important to denote that the random generator w should provide statistically equal numbers of discrete output values in order for the detection procedure to function more accurately. The robustness of the watermark generally increases with the amplitude of the watermarking signal, but the noise poses a limit to this increase.

Watermark Detection
Let us denote by S the following sum: By combining (1), (2) we get: The rst sum in (3) is zero if the random generator produces equal numbers of discrete output values and the signal mean value m x is equal to zero. In case some random output values are more frequently produced this dierence, denoted as w, m ust be taken into account.
Therefore, in (3) On the other hand, if the signal is watermarked, However, x(i) is of the original signal which cannot be used in the detection process.
x(i) can be replaced by y(i) in the last two terms of (4) without signicant error. This replacement leads to the replacement o f P w i=1 x(i)w(i) b y w N S. Therefore, by subtracting the amount w N jSj from S and dividing the result by P N i=1 f(y(i); w (i))w(i), the result r is approximately normalized to 0 or 1. The watermark detector used in this method produces the detection value r given by: The detection value theoretically lies between 0 and 1, yet the approximation of x(i) by y(i) introduces an inaccuracy which slightly expands the interval [0; 1] to [0 "; 1 + "]. Experimentally, a watermark threshold may b e e m bedded above 0 :5, in order to decide whether a certain watermark exists in the signal. The threshold used can be increased if we require increasing certainty in relation to the watermark detection. Figure 1 illustrates the empirical pdf of the detection value r in a watermarked and a non-watermarked signal.
The empirical pdf of a non-watermarked signal is represented by the solid curve, whereas the dashed curve shows the empirical pdf function of the watermarked signal. Both distributions have been calculated using 1000 dierent w atermarks with S NR= 2 6 . Watermark detection attempt of a signal using various keys Watermark key is 444 Figure 2: Detection values in a watermarked signal using various seeds (Key is 444).
The embedding of multiple watermarks causes incremental audible distortion. The maximum number of multiple watermarks to be embedded without audible distortion depends on the amplitude of each w atermarking signal. The worst case considers that the rst watermark reaches the threshold of noise, so the second one will be audibly perceptible even if it is of low amplitude. However, multiple watermarks are being detected in a signal with equal success. In conclusion, a multiple watermarking scheme is possible as soon as the combination of the watermarks is chosen carefully in a way that the whole acoustic result is not audibly perceptible.
The detection algorithm gives no false alarm even when it is tested on a watermarked signal using other wrong watermark keys. For example, 1000 keys, of which only one was valid, have been used to detect a watermark in a watermarked signal. The results are being shown in Figure 2.

Audio Watermark Robustness to Signal Manipulation 4.1 Robustness to MPEG2 audio compression
The robustness of the watermark technique described above, has been tested using Layers II and III of the MPEG Audio. Several 16-bits signed stereo 44.1KHz watermarked signals were encoded using 80 kbps rates in Layer III and 48 kbps rates in Layer II. The lower the rate the bigger is the compression ratio. The watermark resists the encoding-decoding process as shown in Figure 3(a). In this Figure, 1000 distinct watermarks (SNR=26) were embedded into an audio signal producing equal number of distinct watermarked signals. All were compressed by MPEG2 audio Layer III with a compression rate of 80kbps. Watermarking detection after decompression indicates a slight decrease of the detection values in the watermarked signals. The solid curve shows the pdf of the detection values after MPEG2 in comparison with the dashed curve w h i c h indicates the pdf of the same values before MPEG2. Since the detection ratio is always above the 0.5 threshold, we h a ve 100% success in watermark detection in this experiment. Layer II 48kbps causes an audible distortion to the wa-termarked signal, yet the watermark detection is being retained successfully.

Robustness to Filtering
The robustness of the watermark procedure described in this paper was studied under moving average and other types of low-pass ltering. Watermarked audio les were ltered by a moving average lter of length 20 which i n troduces a noticeable audible distortion, yet the watermark is detected. Figure 3(b) shows the alteration in detection values introduced by the use of the above mean lter. In general, the detection values are increased in the ltered signals and this is the reason why the pdf of the detection values of the ltered signals in 3(b) is translated to the right in comparison with the non-ltered respective p d f .
Our watermark is also robust to lowpass ltering. 1000 watermarked audio signals sampled at 44100Hz were ltered by a 25th order Hamming lowpass lter with cut-o frequency 2205Hz. The solid curve of gure 3(c) displays the pdf of the detection values after ltering, while the dashed curve indicates the respective pdf before ltering. It is obvious that the mean value of the solid (ltered) curve is increased in comparison with the dashed (non-ltered) one. The deviation of the solid curve is increased as well, therefore slightly reducing the robustness of the detection scheme after lowpass ltering. In both experiments, we h a ve 100% success in watermark detection.

Robustness to Resampling and Requantization
Watermarked audio signals sampled at 44100Hz have been resampled down to 22050 Hz and 11025 Hz and back again to their initial frequency. Although the above processing caused noticeable distortion in relation to the original signals, the watermarks remained easily detectable. Figure 4 shows how the watermark is retained in 1000 watermarked signals that have been resampled down to 11025 Hz and back to their initial 44100 Hz frequency. In this experiment w e h a ve 100% success in watermark detection. Requantization of the original 16-bit audio signal down to 8-bit samples and backwards conserves the embedding watermark despite the loss of information during the processing. The watermarks resist the requantization process because it is amplitude adaptable with respect to the original signal. Figure 5 shows how t h e watermark is retained in 1000 watermarked signals that have been requantized down to 8-bit and back to 16bit. The deviation of the requantized pdf is increased as in lowpass ltering, thus reducing the robustness of detection. In this experiment w e h a ve 9 9 ; 8% success in watermark detection. All above experiments were held using the same watermark parameters SNR=26.   The watermarking scheme presented above embeds a watermark in the time domain of a digital audio signal by slightly modifying the amplitude of each audio sample. The characteristics of this modication are determined both by the original signal and the copyright owner. The detection procedure does not use the original signal. Our watermarking scheme is statistically imperceptible and resists MPEG compression plus other forms of signal manipulation, such as ltering, resampling and requantization.