Valerio Tenace
email: valerio.tenace@polito.it

Andrea Calimera
email: andrea.calimera@polito.it

Enrico Macii
email: enrico.macii@polito.it

Massimo Poncino
email: massimo.poncino@polito.it

Logic Synthesis for Silicon and Beyond-Silicon Multi-Gate Pass-Logic Circuits

Keywords: Emerging technologies, Graphene, Silicon nano-wires, Pass-Gate Logic, CAD, Logic Synthesis, Low-Power, Adiabatic Computing

In the last decade several new technologies have been proposed as possible replacement for MOSFETs; Silicon Nanowires, Magnetic Tunnel Junctions, Graphene p-n Junctions are just some of the most representative examples. Although their intrinsic differences, they all share a common key characteristic, i.e., enable the implementation of logic gates with an expressive power much higher than that of state-ofart silicon CMOS gates. This may translate into more complex and faster switching functions that count less devices. The view of new materials that can serve as technological vehicles for energy efficient circuits and systems attracted the interested of the whole electronics research community. Apart from the many technological aspects, the path towards large-scale integration of emerging devices crosses the need of (i) new integration strategies that better fit the characteristics of the new technologies and (ii) new computer-aided design (CAD) methodologies able to cope with the complexity of today's design specs. The availability of this two elements may open the way for fast design space exploration and better assessment of new technologies against standard CMOS. This work focuses on logic synthesis and optimization tools for ultra-low power pass-gate circuits mapped into emerging technologies, Graphene and silicon nano-wires. More specifically, we describe a novel multifunction decomposition engine that (i) efficiently performs abstract circuit modeling through a highly-compact data structure called Multi-Function Pass Diagram (MFPD), (ii) provides an effective multi-gate synthesis&optimization flow, (iii) allows accurate power/delay estimations. The contents reported in the following sections represent one of the first examples of how dedicated algorithms and data-structures can substantially improve the quality-of-design when moving from CMOS to emerging technologies. Simulation run conducted on different benchmarks demonstrate that pass-gate circuits synthesized with the proposed tool are smaller and shallower, hence less power hungry and faster than circuits obtained through conventional synthesis methodologies based on standard design flows. As an additional contribution, the results prove that our solution is not only applicable to beyond-silicon technologies but also to standard MOSFETs.

Introduction

CMOS at the end of the line

The introduction of Metal-Oxide-Semiconductor Field-Effect-Transistors (MOS-FETs), officially set in 1947 at Bells Labs as a replacement to vacuum tubes, represents a milestone in the industry of semiconductors. Since then, and after 60-year long research efforts, Complementary MOS (CMOS) electronic circuits have become the dominant technology for the entire ICT segment.

The continuous demand for smaller, faster and more power-efficient Integrated Circuits (ICs) have pushed CMOS technology close to its boundary. At the time being, technology trends are clearly highlighting that a radical shift in thinking digital hardware design might come soon. Among the many aspects, we highlight three well known issues that sustain this claim.

-Non-ideality of the Silicon scaling process: below the 45nm node the technology scaling process faced several limitations due to (i) the increased difficulty in discretizing transistors on a physical die, a problem related to the gate-oxide thickness that is slowly approaching a few-atom width [START_REF] Schulz | The end of the road for silicon?[END_REF];

(ii) the miniaturized gate length of MOS transistors and the upsurge of short-channel effects (SCEs), leakage current in particular, which represent a serious reliability issue [START_REF] Thompson | Moore's law: the future of si microelectronics[END_REF]; (iii) as transistors size decreases, power dissipation and process-variation induced reliability issues become critical [START_REF] Bernstein | High-performance cmos variability in the 65-nm regime and beyond[END_REF]. These issues impact the fabrication yield of reliable ICs. -Nanometric CMOS styles are no longer the most energy-efficient integration strategy: static CMOS has been taken as a reference style for mainstream VLSI circuits due to high noise immunity, resilience to supplyvoltage scaling and low leakage currents. However, as the technology scaling process went below the 90nm mark, some of these characteristics faded out due to SCEs. This suggests that other logic families that were discarded in the past, e.g., Dynamic-Logic, Pass-Transistor-Logic [START_REF] Zimmermann | Low-power logic styles: Cmos versus passtransistor logic[END_REF], may represent a new way out for low-power ICs. -Hitting the power-wall and the dark-silicon problem: achieving ultralow power consumptions is becoming a vital feature for consumer electronics, especially in the context of the Internet-of-Things (IoT) [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF] where always-on, always-connected devices running sensoring applications and data-intensive computing represent the new mainstream paradigm. Even if many lowpower techniques for CMOS circuits and systems are available today [START_REF] Rabaey | Low power design methodologies[END_REF], e.g., Dynamic-Voltage-Frequency Scaling, Power-Gating, Multi-Threshold-Voltage and Reverse-Body-Biasing, the power consumed by CMOS based Systems-on-Chips (SoCs) architectures may exceed the power budget. This implies that an ever larger portion of the silicon die must be kept off (Dark-Silicon). To address this issue, standard SoC architectures will make space to less power hungry solutions that implies the use of dedicated accelerators with embedded memory resources and more energy efficient circuitry.

For such reasons, soon or late, Silicon, CMOS and standard Von-Neumann architectures will drop the scepter in favor of emerging technologies, alternative integration strategies and new architectures. From a technological point of view, recent works proposed several options such as Ambipolar Silicon-NanoWires [START_REF] Marchi | Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire fets[END_REF], Graphene p-n Junctions [START_REF] Chiu | Controllable pn junction formation in monolayer graphene using electrostatic substrate engineering[END_REF], Graphene Nanoribbons [START_REF] Han | Energy band-gap engineering of graphene nanoribbons[END_REF], Magnetic Tunnel Junctions [START_REF] Ikeda | Magnetic tunnel junctions for spintronic memories and beyond[END_REF] and Domain-Wall Nanowires [START_REF] Parkin | Magnetic domain-wall racetrack memory[END_REF]. Apart from their improved electrical characteristics, those technologies could enhance switching primitives with new fascinating properties able to accommodate the specifications of alternative computing paradigms.

Candidates to replace the CMOS technology

The above qualitative analysis suggests that the Silicon/CMOS pair could be soon replaced by some new material and a more energy efficient integration strategy. Among the many options we believe ambipolar technologies, such as Graphene or Silicon-Nanowires, integrated à la pass-gate logic style, a.k.a. passtransistor logic (PTL), represent an interesting option. In particular, as it will be shown later in the text, Graphene-based devices are particularly suited for pass-gate logic.

The choice of PTL is justified by its high intrinsic efficiency, already proven for silicon technologies. PTL circuits can implement logic functions with a lower transistor count, smaller parasitic capacitance and hence better performance [START_REF] Shelar | Bdd decomposition for delay oriented pass transistor logic synthesis[END_REF]. Even today's CMOS libraries make use of PTL for some logic gates, e.g., flipflops and multiplexers, because of their efficient implementation. Moreover, PTL circuits offer an opportunity to work "adiabatically", namely, mimicking the adiabatic (i.e., without energy exchange) charging process [START_REF] Oklobdzija | Pass-transistor adiabatic logic using single power-clock supply[END_REF]. Adiabatic PTL may find space with the implementation of dedicated hardware accelerators in charge of processing "slow" physical-data (e.g., biometric signals) with a very limited energy budget [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF].

The use of PTL and, more precisely, adiabatic PTL, has been already proven for emerging technologies, such as nanoelectromechanical switches (NEMs), carbon nanotubes (CNTs), and graphene p-n junctions. For such devices the PTL style enables the design of logic circuits with improved energy efficiency if compared to CMOS [START_REF] Houri | Limits of cmos technology and interest of nems relays for adiabatic logic applications[END_REF][START_REF] Ding | Cmos-based carbon nanotube pass-transistor logic integrated circuits[END_REF][START_REF] Miryala | Ultra low-power computation via graphene-based adiabatic logic gates[END_REF].

Lack of logic synthesis tools for PTL

It is clear that new hardware schemes, such as PTL, will inevitably ask for new CAD tools for the logic synthesis of digital blocks. Algorithms and data structures for the logic synthesis evolved following the growth of semi-custom CMOS libraries, while synthesis for PTL has been improved only marginally. This is why, even today, PTL remains underutilized [START_REF] Shelar | Bdd decomposition for delay oriented pass transistor logic synthesis[END_REF]. It's not a coincidence that most of the previous works do focus on circuits for very specific arithmetic functions [START_REF] Suzuki | A 1.5-ns 32-b cmos alu in double pass-transistor logic[END_REF][START_REF] Lee | Application of dynamic passtransistor logic to an 8-bit multiplier[END_REF] or handcrafted basic Boolean logic gates [START_REF] Zimmermann | Low-power logic styles: Cmos versus passtransistor logic[END_REF][START_REF] Wu | Low-leakage and low-power implementation of high-speed 65nm logic gates[END_REF]. Indeed, when the target design turns into random logic, standard multi-level synthesis engines can't exploit the structural properties of PTL. That brings to sub-optimal implementations that typically require ad-hoc actions at the post-synthesis stage.

This problem is not new to the research community and several solutions have been introduced in the last years. Most of them, if not all, are closely related to the concept of Binary Decision Diagrams (BDDs) or some of its variants [START_REF] Bertacco | Decision diagrams and pass transistor logic synthesis[END_REF][START_REF] Shelar | Bdd decomposition for delay oriented pass transistor logic synthesis[END_REF][START_REF] Amaru | Biconditional binary decision diagrams: A novel canonical logic representation form[END_REF]. There are two main reasons behind the use of BDDs. First, there exists a one-to-one matching between the BDD representation of the logic function and the final PTL circuit implementation; this enables the concept of one-pass logic synthesis [START_REF] Drechsler | Towards One-Pass Synthesis[END_REF] where logic optimization and technology mapping are carried out concurrently on the same data structure thereby saving CPU and memory usage. Second, BDDs [START_REF] Somenzi | Cudd: Cu decision diagram package release 2.3. 0[END_REF] are a very mature data-structure with lots of available optimization algorithms for redundancy removal and circuit optimization.

Despite the efficiency of BDDs as data-structure is unquestionable, BDDbased synthesis tools show many limitations. First, the tree-like structure of BDDs reflects into a deep circuit topology with large depth, and hence large propagation delays. Second, state-of-the-art decomposition methods for BDDs construction all operate using a pre-fixed variable-order (VO), namely, the order used for variable expansion is fixed during the entire decomposition procedure, no matter what the logic function is. Since V O affects the vertex-set cardinality of BDDs, a wrong V O might result into dramatic area increase of the resulting circuit. Third, decomposition methods are constrained to a "singlefunction" decomposition. Such a function, here referred as g(X), differs depending on the type of BDD variant in use, e.g., MUX for standard BDDs [START_REF] Somenzi | Cudd: Cu decision diagram package release 2.3. 0[END_REF], XOR for Biconditional-BDDs [START_REF] Amaru | Biconditional binary decision diagrams: A novel canonical logic representation form[END_REF]. Logic circuits dominated by g(X), e.g., XOR-rich arithmetic circuits, take advantage of this characteristic, others, like random logic circuits, may suffer from sub-optimal minimization. While the first two issues have been addressed in [START_REF] Tenace | One-pass logic synthesis for graphene-based Pass-XNOR logic circuits[END_REF] with the introduction of the Pass Diagram (PD) data-structure and the non-fixed V O decomposition, this work elaborates on the third issue, i.e., how to overcome "single-function" decomposition.

Contribution of this work

As an extension of the contents proposed in [START_REF] Tenace | Multi-function logic synthesis of silicon and beyond-silicon ultra-low power pass-gates circuits[END_REF], this work gives a comprehensive description of efficient abstract models and data-structures that are particularly suited for the synthesis of Multi-Gate Pass Logic (MGPL) circuits mapped with emerging technologies, Graphene and Silicon-NanoWires in particular, or, alternatively, with standard silicon MOSFETs.

An MGPL circuit consists of series connections of two-input pass-gates that can be turned-ON (OFF) and thus open (close) an electrical path between a clocked-power (the source) and the main output (the leaf); multiple paths are connected in parallel making the final logic circuit. Hence, similar to PTL, the information is not carried in the form of charges stored in parasitic capacitance, but rather through the root-to-leaf propagation of the clock-power signal. It is worth noticing that, differently from any other existing PTL solutions, MGPL makes use of pass-gates that embed multiple Boolean operators, like AND, OR, NAND, and not just MUX or XOR as in the previous works; the choice of which operators depends on the technology in use.

We introduce a novel abstraction model, namely, the binary Multi-Function Pass-Diagram (MFPD), a graph-based representation for k-ary Boolean functions. An MFPD is a polarized, acyclic directed graph made up of N root-to-leaf logical paths. Each path is composed of an arbitrary number of two-input nodes connected in series, where each node represents a binary connective between two, out of k, primary input variables and can assume either a TRUE logical value, e.g., closed switch, or a FALSE logical value, namely an open switch. Under a specific input pattern, logical paths can be activated (all nodes are closed switches) in mutual exclusion (1 path out of N ) and thus create a gateway from the root to the leaf. In such case, the equivalent logic function represented by the MFPD is evaluated as TRUE; on the contrary, when no active paths do exist, the logic function is said to be evaluated as FALSE. This structure matches the topology of a Multi-Gate Pass-Logic circuit.

The construction of a binary MFPD encompasses two major steps: multifunction decomposition using a set of basic Boolean operators, e.g., AND, OR, XOR and their complement; and redundancy removal through iterative reduction rules. Those phases have been integrated into an automatic synthesis and optimization tool named Kanon. Moving from single-to multi-function decomposition can be conceptually seen as the shift from two-level to multi-level synthesis carried out for CMOS circuits.

We apply our tool Kanon to a sub-set of generic benchmarks mapped onto three different technologies, i.e., Silicon MOS transistors, Ambipolar Silicon Nanowires and Graphene p-n junctions. The use of generic benchmarks avoids biased results due to the presence of circuits dominated by a specific function, the use of different technologies demonstrates that the proposed solution well fits both silicon and beyond-silicon technologies. The obtained MGPL circuits are then compared against standard PTL circuits synthesized using state-of-art BDD-based tools. The collected results validate the functionality of the proposed MFPD model and the related multi-function decomposition, whilst simulations using SPICE models quantify the energy efficiency of MGPL circuits.

Multi-Gate Pass Logic

A first example of pass-logic circuit for emerging devices has been recently proposed in [START_REF] Tenace | Pass-XNOR logic: a new logic style for PN junction based graphene circuits[END_REF] in the form of Pass-XNOR Logic (PXL) network using graphene p-n junctions. A PXL circuit consists of a network of Pass-XNOR Gates (PXGs); PXGs connected in series form a logic path, while logic paths connected in parallel connect the root of the circuit (fed by a clock-power signal) to the leaf (the main output). The clock-power signal works as an evaluation signal that eventually reaches the output when at least one parallel logic path is ON; in this case the logic function is evaluated as TRUE, i.e., 1-logic. When none of the parallel logic paths is ON, the propagation of the clocked-power signal is inhibited and the logic function is evaluated as 0-logic.

! " ! " #$% ! # ! $ ! % ! & '()* +, -. & ' '()* +, -" & ' ()*+,-$. ,/0.1/123$3,42 ! #5% ! " ! % ! # ! $ ! & 67$.8$3,429+,:2$. #;% #-% ! " /() " * ) # , ! # /() $ *", ! $ /() $ * ) & , ! & /() & *", ! % /() $ * ) % , <451951+-=,03,42 Fig. 1. MGLP circuit example, where f = (x1¬∨x2) ∧ [(x3¬∨1) ∨ ((x3¬∨x4) ∧ (x4¬∨1))] ∨ (x3¬∨x5)
A logic path is ON iff all its series connected PXGs are ON simultaneously. The PXGs can be seen as logic primitives whom electrical behavior resembles a CMOS transmission gate with an embedded XNOR Boolean functionality. More specifically, each PXG is electrostatically controlled through primary input logic signals that tune the equivalent resistance of the PXG itself; a PXG fed by logic signals having same polarity shows a low-resistance, the ON state, whereas logic signals with opposite polarity lead the PXG to high-impedance, the OFF state.

As a further step to achieve a higher level generalization of the Pass-XNOR Logic (PXL) style, [START_REF] Tenace | Multi-function logic synthesis of silicon and beyond-silicon ultra-low power pass-gates circuits[END_REF] introduces the concept of Multi-Gate Pass Logic (MGPL). The physical primitives of an MGPL network are generic pass-gates (PGs), that, from a functional point of view, can be seen as function-controlled switches. Similar to PXGs, they consist of two logic-terminals fed by the input logic signals (x and y in Figure 1-(b)), and two transmission terminals, one playing as the source of an evaluation signal and the other as the collector (S and D in Figure 1-(b)). The control function is a two-input Boolean operator g(x, y) between the x and y logic inputs; when g(x, y) = 1 the PG is ON (low-resistance), Figure 1-(b), when g(x, y) = 0 the PG is turned OFF (high-impedance), Figure 1-(c). PGs with different control functions can be designed depending on the technology in use; the example in Figure 1 is for a NAND-PG, i.e., g(x, y) = x¬∨y. Notice that an MGPL circuit can contain PGs with different embedded functions. Similar to PXL, an MGPL (Figure 1-(d)) consists of logic paths connected in parallel between a clocked-power supply (the root) and the main output (the leaf). Each path consists of a cascade of independent PGs driven by primary inputs. When activated (all PGs turned-ON), a logic path creates a low-resistive gateway through which the clocked-power signal can flow from the root to the leaf. Under this condition the circuit's output is evaluated as 1-logic. Logic paths are in mutual exclusion by construction, that is, for a given input pattern one and only one path can be eventually activated. When there are no activated paths the circuit's output is evaluated as 0-logic. An MGPL circuit can be modeled using a new dedicated abstract model, the Multi-Function Pass-Diagram (MFPD), Figure 1-(a), described in the next section.

As for other dynamic logic families, the logical computation of MGPL circuits consists of two distinct phases: the configuration phase and the evaluation phase. During the former, primary logic inputs, i.e., the literals composing the logic function, are fed to the logic inputs of the pass-gates. At the end of this phase the doping profile of each and every device is fixed and the resistive paths of the network are set up. In the evaluation phase the clocked power signal is precharged and propagated through the network. A pulse detected on an output leaf evaluates the implemented function as TRUE; in this regard, a Sense Amplifier can be used for each output cone in order to quickly identify the 1-logic and reshape the clock-supply signal [START_REF] Tenace | Quasi-adiabatic logic arrays for silicon and beyond-silicon energy-efficient ics[END_REF].

It is worth emphasizing that although the MGPL resembles the PTL structure, the difference is substantial. In PTL circuits, transistors are used as switches that deviate the current flow to different paths; on the contrary PGs are used as switches to open/close a logic path. This is reflected by the model used to represent the circuit. Indeed, BDDs are not the most intuitive representation as PG gates do not implement any deviation of the signal. Second, while in PTL an output is always connected to a static power supply terminal, V dd if '1' or Gnd if '0', output evaluation in MGPL logic is dynamic: current is flowing if '1', not flowing if '0'. Alternatively, one can see MGPL circuits as a half way between CMOS and PTL. As in CMOS series/parallel connections between gates are available, as in PTL, information is carried out by means of root-to-leaf current flow.

Pass-Gate Devices

New logic primitives introduced by emerging technologies represent a perfect fit to the structure of PGs. Figure 2 pictorially describes some of them. In particular, Figure 2-(a) shows four PG embodiments using Ambipolar Silicon-NanoWires (SiNW) [START_REF] Marchi | Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire fets[END_REF]. The first two (left) are composed of a single SiNW transistor and implement the AND and NOR logic gates. The remaining two (center and right) consist of a pair Si-NW transistors and implement the XNOR or XOR logic gates.

Figure 2-(b) shows two possible pass-gates using standard MOSFET transmission-gates. The first one (left) implements the AND, whereas the second one (right) implements the NOR. Since both configurations require four MOSFETs, silicon devices have less expressive power when compared to SiNWs.

Finally, Figure 2-(c) shows pass-gates mapped on graphene p-n junctions [START_REF] Miryala | Ultra-low power circuits using graphene p-n junctions and adiabatic computing[END_REF]. A graphene p-n junction consists of two metal back-gates (blue and green triangles) driven by logic signals (x and y). Logic signals with same polarity turn the junction ON. The first PG (top left) implements the NOR gate; the outer input connections x and y are both compared to a logical-0 reference. It works as follows: when both x and y are set to 0-logic, the input evaluation signal (red

! " !#$ % " $! $" !# & " ! " $! $" !#$'" !"#$%&'() *$+,-. $! $" ! " !# & " $! $" ! " !#$ % "
/0*12345(..43)(6.$.7&)48&9$: ramp) is allowed to propagate; in all the remaining cases at least one p-n junction is OFF and the evaluation signal is stopped. Similarly, the second pass-gate (bottom left) implements the AND; the evaluation signal propagates iff both x and y are fed wit 1-logic. Notice that for NOR and NAND SiNWs need less devices (1 vs. 2). The last two pass-gates (top and bottom right) implement the the XNOR and XOR gates. In this case graphene shows higher expressive power than SiNW. It is therefore clear how different technologies can be better exploited using different logic primitives.

! " ( ( !#$ % " ! " !#$'" ! " ) ) !# & " ;)(%<=6=4%+64>?6:7$&6. @(A @#A @:A $! " ! $" !#'" $! " !#'"

Delay and Power Modeling of MGPL circuits

The total delay D p of an MGLP logic circuit can be estimated as the sum of delays due to the configuration phase D conf and the evaluation phase D eval , as described in [START_REF] Schulz | The end of the road for silicon?[END_REF], where D conf is the time primary logic inputs take to charge

D p = D conf + D eval (1)
the parasitic capacitances at the back-gates, whereas D eval is the propagation delay of the input pulse through the front resistive paths of the network. The amount of power consumed during the configuration phase P c is due to charging/discharging of the input gate capacitance of the PGs. For a circuit made up N gates, an approximate, yet accurate model borrowed from CMOS is reported in (2), with P P Gi as the power consumed from the i-th PG, V dd as the supply voltage, f the operating frequency, C i the input capacitance of the i-th PG, and E SWi,j representing the probability that the input signal makes a transition.

P c = N ∑ i P P Gi = N ∑ i 2 ∑ j=1 0.5V 2 dd • f • C in • E swi,j (2)
During the evaluation phase, once primary inputs have settled and PGs have been turned-ON or OFF, the circuit simply reduces to an equivalent resistor R eq , i.e., the sum of the ON resistances R ON of the PGs belonging to the ON-path, in series with the output load capacitance C l . The average power consumed P e can be therefore obtained as described in [START_REF] Bernstein | High-performance cmos variability in the 65-nm regime and beyond[END_REF], where t rf is rise/fall output transition time, and i C l (t) is the current charging C l . Notice that P e is consumed iff the output is TRUE, while it is almost zero otherwise.

P e = 1 t rf ∫ t rf 0 R eq i 2 C l (t)dt = R eq C 2 l t 2 rf V 2 dd (3)
Moreover, for values of T rf large enough, the evaluation phase completes at zero-power, namely, adiabatically.

Building MFPDs

Multi-Function Decomposition

The decomposition of a logic function through the primitives made available by the technology in use represent a fundamental step of any logic synthesis algorithm. Since most techniques leverage multi-level logic representations, in this section we illustrate an ad-hoc decomposition that is fine-tuned for passgates logic. Such decomposition, named multi-function decomposition, relies on the basic assumption that any Boolean equation given in the form of sum-ofproducts (SOPs), or product-of-sums (POSs), can be decomposed by means of a user-defined set of logic connectives G = {g : B 2 → B}. Let us assume a function f (S) with support-set S = {x 1 , x 2 , x 3 } described with the following SOP:

f (S) = (x 1 ∧ ¬x 4 ) ∨ (¬x 1 ∧ ¬x 2 ∧ x 3 ) ∨ (x 1 ∧ x 2 ∧ x 3 ) (4)
By resorting to the distributive property and the identity rule, it is possible to expand the function f (S) as a sequence of cubes, having cardinality of two literals:

f (S) = (x 1 ∧ ¬x 4 ) ∨ (¬x 1 ∧ ¬x 2 ) ∧ (x 3 ∧ 1) ∨ (x 1 ∧ x 2 ) ∧ (x 3 ∧ 1) (5)
Each product can then be rewritten using the Boolean connectives g ∈ G by means of duality. For instance, let us assume the availability of two connectives G = {{x ¬ ∨ y}, {x ¬⊕ y}}, where the first one, the NOR (¬∨ symbol), has higher priority, i.e., is processed first. This means that the function f (S) could be NOR-decomposed as shown in [START_REF] Rabaey | Low power design methodologies[END_REF].

f (S) = (¬x 1 ¬∨x 4 ) ∨ (x 1 ¬∨x 2 ) ∧ (¬x 3 ¬∨¬x 3 ) ∨ (¬x 1 ¬∨¬x 2 ) ∧ (¬x 3 ¬∨¬x 3 ) (6)
Such reformulation reveals that (¬x 3 ¬∨¬x 3 ) is a common term, that can be factorized as reported in [START_REF] Marchi | Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire fets[END_REF].

f (S) = (¬x 1 ¬∨¬x 4 ) ∨ (¬x 3 ¬∨¬x 3 ) ∧ [(x 1 ¬∨x 2 ) ∨ (¬x 1 ¬∨¬x 2 )] (7)
At this point, the second operator in G, the XNOR (¬⊕ symbol), could be applied on [START_REF] Marchi | Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire fets[END_REF] in order to further reduce the number of literals in [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF]. Indeed, the term (x 1 ¬∨x 2 ) ∨ (¬x 1 ¬∨¬x 2 ) can be represented as the XNOR between x 1 and x 2 .

We refer to this operation as Boolean substitution. Eventually, the final result of the multi-function decomposition, the original function ( 4) is decomposed as described in [START_REF] Chiu | Controllable pn junction formation in monolayer graphene using electrostatic substrate engineering[END_REF].

f (S) = (¬x 1 ¬∨x 4 ) ∨ (x 1 ¬⊕x 2 ) ∧ (¬x 3 ¬∨¬x 3 ) (8)
Similarly, it is possible to assume a library of logic connectives described as G = {{x¬ ∧ y}, {x¬⊕y}}, where the symbol ¬∧ denotes the NAND operator. In this case, the same Boolean function described in ( 4) is NAND-decomposed as described in [START_REF] Han | Energy band-gap engineering of graphene nanoribbons[END_REF], and thus optimized by means of the XNOR connective, as reported in [START_REF] Ikeda | Magnetic tunnel junctions for spintronic memories and beyond[END_REF].

f (S) = (¬x 1 ¬∧¬x 4 ) ∨ ¬(¬x 1 ¬∧¬x 2 ) ∧ (¬x 3 ¬∧x 3 ) ∨ (¬x 1 ¬∧x 2 ) ∧ (¬x 3 ¬∧x 3 ) (9) f (S) = (¬x 1 ¬∧¬x 4 ) ∨ (x 1 ¬⊕x 2 ) ∧ (¬x 3 ¬∧x 3 ) (10)
It is easy to check the Boolean equivalence between ( 8), [START_REF] Ikeda | Magnetic tunnel junctions for spintronic memories and beyond[END_REF] and the original function (4); in terms of savings, both ( 8) and [START_REF] Ikeda | Magnetic tunnel junctions for spintronic memories and beyond[END_REF] show 25% literal savings. As far as the efficiency is concerned, the proposed multi-function decomposition is closely related to (i) the set of Boolean operators and (ii) their priority ordering in G. Although several options do exist, we resort to a technologyinstructed strategy, namely, available operators in G are sorted, from highest to lowest, in terms of their expressive power (EP), which describes the ratio between the complexity of the logic operator and the number of devices needed to implement the corresponding logic gate. This guarantees the high flexibility and orthogonality of our tool onto different technologies.

As will be shown later in the text, different primitives are used during different stages of the multi-function decomposition. For the sake of clarity we define the first operator in G, the one with the highest EP, as the primary primitive, the remaining ones as the secondary primitives.

( " ! -#.$ " % $ * ' ( & ! -#$ " % $ & ' ( ) ! -#.$ ) %-' ( * ! -#.$ " % .$ & ' ( + ! -#.$ ) %-' ( , ! " #$ " % $ & ' @$'(-'()0,/5+/$& / 0 1! -0 $ 2 . 3 $4 % ! " 0 $ 2 .

5$4 6

A/2,4,B-$"-0$&&(0+/?()-C4D C2D C0D Fig. 3. MFPD of function of Equation ( 6) before optimization (a), after merging of common sub-graphs (b), and after Boolean substitution (c).

Multi-Function Pass Diagrams (MFPDs)

The synthesis of MGPL circuits needs an abstract model for reasoning and optimization. We introduce the MFPD, a simple, yet efficient abstract model for one-pass synthesis of MGPL circuits. Given a generic multi-input/single-output Boolean function f with supportset S = {x 1 , ..., x N }, its MFPD (Figure 3) representation is a polarized, directed acyclic graph defined as G = (Φ ∪ V ∪ Θ ∪ A). The set of internal nodes v ∈ V are labeled as g(x, y), with g ∈ G a two-input primitive Boolean connective and x, y ∈ S. Each internal node v has one outgoing edge a ∈ A representing the logical conjunction (AND) with the successor node. The terminal node with indegree 0 represents the root of the MFPD, where the function starts to be evaluated; the terminal node with outdegree 0 is the leaf of the MFPD, the output of the function f . Multiple output functions are represented by many MFPDs as the number of outputs. As an example, Figure 3-(a) shows the MFPD structure for the function [START_REF] Rabaey | Low power design methodologies[END_REF] with g 0 = (x i ¬ ∨ x j ) and g 1 = (x i ¬⊕x j ).

The main strengths of an MFPD are three. First, they guarantee the capability of supporting multi-function decomposition. This degree of freedom comes at the cost of canonicity, that is, MFPDs do not have an unique representation of Boolean formulae. However, relaxing the canonicity constraint is a wellaccepted concept in the EDA community; indeed, And-Inverter Graphs (AIGs) integrated into commercial multi-level logic synthesis tools are non-canonical representations, but nonetheless they are likely used because more compact and manageable. Second, a MFPD has a 1-to-1 mapping to the final circuit implementation, that is, each internal node is implemented by a single logic primitive in the resulting network (please refer to Figure1-(a)). This makes the MFPD a universal model for both the optimization stage and the technology mapping, a key aspect for one-pass logic synthesis [START_REF] Drechsler | Towards One-Pass Synthesis[END_REF]. Third, but not for importance, MFPDs may serve as model for MGPL circuits mapped using different emerging devices. As an example, Figure 4 depicts a generic MFPD internal node, with f = x¬⊕y, and its implementation using Graphene p-n junctions, Silicon-NanoWires, Magnetic Tunnel Junctions and Memristors. Thus, the proposed MFPD model and its synthesis methodology can be seen as orthogonal tools for the assessment of a wide range of emerging technologies.

Algorithms

Building MFPD

Algorithm 1 describes the pseudo-code of the Build routine we implemented for multi-function decomposition and MFPD construction.

The main input parameters are (i) a tabular description T of the Boolean function and (ii) the primary connective (the first operator in the list of primitives G). Table T can be a non-minimized implicant table ( i.e., not prime) and can be obtained through any Verilog compiler, e.g., ABC [START_REF] Synthesis | Abc: A system for sequential synthesis and verification[END_REF]. We refer to T as the PLA table. As an example, Table 1 shows the PLA table for the Boolean function [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF], where the character '-' identifies a dont'care. The MFPD is generated branch-wise, that is, for each row of the PLA table, i.e., for each product term of the function, nodes are appended in series by iterating the following sequence of operations:

x 1 x 2 x 3 x 4 f 1 --0 1 0 0 1 -1 1 1 1 -1 Algorithm 1: MFPD build Input: PLA Table T , Primary connective g 0 ∈ G Output: Multi-Function PD M F P D 1 M F P D = ∅ 2 foreach row R ∈ T do 3 CU BES R = ∅ 4 DontCareSet = DetermineDCS(R)
Cube sequence generation (line 3-9) -variables not belonging to the don'tcare set are included in the cube list CU BES R in order of appearance; those belonging to the dont-care set are dropped. For odd sequences, the last variable is paired with '1' logic so as to maintain Boolean equivalence. For instance, considering Table 1, for the first row CU BES 1 = {(x 1 , ¬x 4 )}, for the second row CU BES 2 = {(¬x 1 , ¬x 2 ), (x 3 , 1)}, for the third row CU BES 3 = {(x 1 , x 2 ), (x 3 , 1)}.

Node generation (line 10-14) -for each pair of cubes stored in CU BES R , the polarity of the variables are fixed according to the primary Boolean connective g and the resulting nodes are appended on the current branch. Let us consider CU BES 2 which contains two cubes, (¬x 1 , ¬x 2 ) and (x 3 , 1); with g the NOR operator (like the example in Section 3.1), variables are complemented (by De-Morgan) as (x 1 , x 2 ) and (¬x 3 , ¬x 3 ) respectively.

Given a table T with N implicants and M literals, the proposed build routine has a complexity of O(N • M ).

Optimization

Algorithm 2 describes the pseudo-code of the optimization stage for redundancy removal. It implements two different optimization techniques: (i) node elimination by Boolean substitution; (ii) merging of isomorphic sub-graphs. While the latter is reminiscent of standard reduction rules from BDDs [START_REF] Somenzi | Cudd: Cu decision diagram package release 2.3. 0[END_REF], the former one

Algorithm 2: MFPD optimization algorithm

Input: is an ad-hoc strategy for MFPDs. Its purpose is to find suitable equivalent logic connectives, among the list of secondary connectives in G, that can be eventually substituted in order to enable node elimination and reduce the MFPD cardinality; as illustrated in the examples of Section 3.1. Please note that secondary connectives are selected with a greedy approach, that is, the first one that satisfies the Boolean equivalence is instantiated in the network.

M F P D, Secondary connectives G = (g 1 , . . . g m ) ∈ G Output: Optimized Multi-Function PD OM F P D 1 OM F P D = ∅ 2 foreach path P ∈ M F P D do 3 C M ← ∅ 4 C E ← ∅ 5 foreach path Q ∈ M F P D, with Q ̸ = P do 6 if SameSupport(P , Q) then 7 if CheckBoolSub(P , Q, G) then 8 C E .append(Q, g k ∈ G)
Input parameters of Algorithm 2 are the MFPD obtained through the MFPD Build routine, and the list of secondary connectives G ∈ G.

Candidate selection (line 3-15) -Each root-to-leaf path P of the MFPD is compared with any other path Q (P ̸ = Q). If (line 6) P and Q share the same support set (i.e., nodes in P and Q are driven by the same literals) the algorithm checks (line 7) whether it is possible to perform a Boolean substitution, namely, it checks whether some of the operators associated with the nodes in Q can be substituted with some other operator g k ∈ G s.t. Boolean equivalence is satisfied. If so, P and Q share a common node expressed by means of g k , that allows to merge P and Q in a single path. Therefore, Q is stored in the candidates list C E together with the connective g k that enables its elimination. If P and Q do not have common support set (line 10), the algorithm checks whether a path Q shares at least one node with P ; if so, Q is a potential candidate for node merging and it is temporarily stored in the list of candidates C M .

Merge and Eliminate (line 16-20) -once candidates have been selected, the algorithm first evaluates whether there exists at least one candidate for node elimination by Boolean substitution (|C E | > 0). If so, the common node between P and C E is replaced with the new connective g k , and redundant paths in C E are removed (ApplyBoolSub function). If not and the list C M is not empty, then common nodes between C M and P are evaluated for merging through the MergeIsomorphic function. Since Boolean elimination guarantees higher benefits in terms of node count and circuit complexity, e.g., it reduces the number of common branches due to merge operations, this characteristic is exploited first during the last phase of the optimization process with the M ergeAndRemap function. Otherwise, common nodes between the CAN DIDAT ES M list and P are merged by means of the M ergeM axSharing function. The final result is then appended in the optimized MFPD structure OM F P D. Applying this procedure to the MFPD depicted in Figure 3-a allows us to achieve a more compact representation of the same function by means of only three logical nodes/operations, as depicted in Figure 3-b.

Concerning complexity, since each path P is compared with any other path Q, the total number of loops is N •(N -1)

2

, with N the number of paths in the starting MFPD. The complexity of the optimization routine is O(N 2 ). Notice that all other sub-routines have a O(1) complexity (operations are completed in constant time) except for functions SameSupport and SharedN odes which show a complexity of O(M ), with M the number of nodes in the path Q.

Simulation Results

Experimental results reported in this section provide a fair comparison of MFPDs and the resulting MGPL circuits mapped onto different technologies against state-of-the-art data-structures and PTL circuits. The goal is to demonstrate that:

1. MFPDs optimized with the eduction rules described in Section 3 give substantial savings. 2. MFPDs represent the most compact solution for the representation of switching functions implemented through the MGPL style; metrics adopted are expressive power, namely the number of nodes and depth, i.e., nodes count along the longest path. 3. MFPDs are a true technology-independent abstract model, namely, the way they model a Boolean function can be orthogonally applied to any kind of technology and, most importantly, whatever the logic primitives are.

4. MGPL circuits obtained through MFPDs might become the vehicle for ultralow power computing using emerging technologies, graphene in particular; in this regard, we show that the MGPL style allows large gains w.r.t. PTL and, most importantly, it is well suited for ultra-low power digital circuits.

We set up five different synthesis flows, the first four are for pass-gate logic circuits, the target of this work, the fifth one is for standard cells-based circuits.

-MFPDs (the solution proposed in this work): circuits described using the PLA format [START_REF] Synthesis | Abc: A system for sequential synthesis and verification[END_REF] are processed with our tool Kanon for multi-function decomposition using the connective set G = {{x¬ ∨ y}, {x¬⊕y}, {x ⊕ y}}.

It is worth to notice that even though more Boolean operators can be used, here we force our tool working in worst-case conditions where only three primitives are allowed. Resulting MFPDs are then mapped onto MGPL circuits using different technologies.

-PDs (introduced in [START_REF] Tenace | One-pass logic synthesis for graphene-based Pass-XNOR logic circuits[END_REF]): circuits described using the PLA format [START_REF] Synthesis | Abc: A system for sequential synthesis and verification[END_REF] are processed leveraging Gemini, a single-function XNOR decomposition tool; resulting PDs are mapped onto PXL circuits using different technologies.

-Biconditional-BDDs (described in [START_REF] Amaru | Biconditional binary decision diagrams: A novel canonical logic representation form[END_REF]): circuits are first synthesized using a standard multi-level synthesis tool and then translated into BDDDs using single-function XOR decomposition scheme; the resulting BBDDs are mapped onto a tree-based PTL-like structure using different technologies.

-BDDs: circuits are processed with a C program that leverage the CUDD package [START_REF] Somenzi | Cudd: Cu decision diagram package release 2.3. 0[END_REF]; BDD structures, obtained with a single-function MUX-based decomposition, are mapped on PTL-like circuit using different technologies.

-AIGs: obtained with the ABC synthesis tool [START_REF] Synthesis | Abc: A system for sequential synthesis and verification[END_REF], the AIGs are mapped on a CMOS library containing only AND and INV gates; it is worth emphasizing that AIGs cannot be directly used for pass-gates logic circuit, however, they serve as a reference point to better evaluate MFPDs.

The experiments were run on a set of open-source benchmarks from the LGSynth91 suite [START_REF]Collection of digital design benchmarks[END_REF], and accurate SPICE simulations were used for the characterization of the obtained netlists. Please note that the size of such benchmarks is comparable to that of those used in other synthesis-related works, e.g., [START_REF] Amaru | Biconditional binary decision diagrams: A novel canonical logic representation form[END_REF]. Without loss of generality, only combinational logic cones have been considered for synthesis, i.e., in-to-out and register-to-register logic cones.

Efficiency of reduction rules during MFPD optimization

Table 2 gives a brief description of the adopted benchmarks and an overview of the efficiency of the algorithms proposed in this work. Columns PI, PO and I represent the total number of primary inputs, primary outputs and implicants of each benchmark. Under the label Number of nodes, column w/o opt refers to MFPDs after the build process, whereas column w/ opt refers to MFPDs after optimization; column Savings reports optimization gain; As the table suggests, the proposed reduction rules allow about 40% of savings on average. Noticeably, large savings have been recorded for all the benchmarks, except for o64. For this case we observed the PLA table is a diagonal matrix of '1s' which prevents MFPD optimization.

Compactness of the MFPD model and execution time

Figure 5 depicts the obtained synthesis results averaged over all the benchmarks described in Table 2. The plot suggests that MFPDs outperform BBDDs, which are 35.39x larger, BDDs (15.51x larger) and PDs (2.1x larger); only AIGs are more compact (0.63x). Indeed, AIGs leverage two key options available in multilevel optimization, namely the possibility of reusing cascades of common sub- expressions and local don't-care conditions, a technique that is not applicable to pass-gates logic styles. However, an important aspect concerns the depth of the data-structures. In this case MFPDs are the most efficient solution since BBDDs (21.12x deeper), BDDs (20.33x deeper) and PDs (1.83x deeper) show an higher number of devices on the longest path. AIGs do the same as they return circuit topologies 3.83x deeper. Therefore, MFPDs are well suited for pass-gates logic circuits, where smaller depth translates into shorter delays and smaller voltage noise.

Such huge savings achieved are the consequence of the efficient multi-function decomposition, in particular: (i) the availability of more Boolean operators w.r.t. BDDs, BBDDs and PDs, (ii) the fact that inputs variables belonging to the dont-care set are dropped during decomposition (please refer to Algorithm 1), (iii) the regularity of the implication table that allows large minimization (see Algorithm 2).

From a complexity viewpoint, the barchart in Fig. 6 reports the average CPU execution time of the Kanon tool compared to the BBDD package. It turns out that MFPD synthesis is, on the average, 38x faster w.r.t. the procedures used for BBDDs. As a representative example, for the largest benchmark (s13207.1) the MFPD is built and optimized in 7.08s, whereas the equivalent BBDD takes 241.9s. This is due to the lower computational workloads of MFPD algorithms which do not require the reconstruction of the network graph during optimization.

Many technologies, one synthesis methodology

To demonstrate the "orthogonality" of both the MFPD model and the MGPL style over different technologies, we mapped the benchmarks under analysis using three different devices: graphene p-n junctions (Graphene), Ambipolar Silicon NanoWires (Si-NWs) Pass-Transistors (Si-NW PT), and traditional MOSFETbased Pass-Transistors (Si-MOS PT). As described in Section 2.1, each of these technologies has different "optimal" primitives, namely the ones with the highest expressive power. Hence, tools that can seamlessly use different logic primitives may represent a genuine solution for the evaluation and comparison of different emerging technologies. Figure 7 summarizes the post-synthesis results obtained using our tool. Since MFPDs are a superclass of Pass Diagrams, we only provide comparison against BBDD-based synthesis. BBDDs represent the most recent solution proposed for emerging technologies [START_REF] Amaru | Biconditional binary decision diagrams: A novel canonical logic representation form[END_REF] and their superiority w.r.t. other solutions have been already demonstrated. Notice that MFPDs nodes can be mapped with NOR, XOR and XNOR, while BBDDs only allow XOR mapping. Each of this passgates count different devices according to the adopted technology (Fig. 7). As a result of the multi-function decomposition, circuits synthesized using MFPDs are several orders of magnitude smaller in size; this translates into more area and more power efficient MGPL circuits.

Power and Performance efficiency of MGPL circuits

The extremely compact structure of MGPL circuits allows very high power/energy reduction. While this is an intuitive conclusion, here we underline the energy efficiency of the MGPL style for emerging technologies, Graphene in particular. Figure 8 provides a technological comparison between Graphenebased MGPL circuits and Silicon-MOS PTL circuits. The plot shows the powerdelay product (PDP) averaged over all the benchmarks as function of the transition time T r of the input signals. The plot highlights the "adiabatic" nature of both implementations, i.e., PDP reduces as T r increases. For a T r that ranges from 1 to 1000 ps (3 orders of magnitude), the PDP of graphene reduces by more than 5 orders of magnitude, whereas that of silicon reduces only by 3 orders of magnitude. However, and this is the most important aspect, graphene circuits are more energy efficient, not just in terms of absolute numbers, a result due to the intrinsic characteristics of the material [START_REF] Tenace | One-pass logic synthesis for graphene-based Pass-XNOR logic circuits[END_REF]), but also in terms of "scalability". This concept is further explained in Fig. 9 that correlates dynamic power consumption over transition time. As the plot suggests, for T r ∼ = 1ps, namely outside the adiabatic region, PTL circuits are more power efficient, but as T r increases, the adiabatic nature of the MGPL circuits shows reaching a power consumption that is about 2 order of magnitude lower that the PTL counterpart (best case at T r ∼ = 1ns).

Conclusions

In this work we introduced a novel abstract representation for Boolean switching functions: the MFPD. Such a new data-structure, obtained with a multi-function logic decomposition, allows the implementation of compact MGPL circuits that well fit the characteristics of new emerging devices.

Results obtained with our tool Kanon demonstrate that MGPL circuits show superior characteristics w.r.t. state-of-art solutions, in particular (i) larger area efficiency (almost 15.51x better than PTL circuits obtained with BDDs) and (ii) shallower logic paths (77% w.r.t. CMOS circuits obtained with AIG-based multi-level synthesis).

These achievements demonstrate that there is a huge margin of improvement when moving to new technologies and that solutions universally recognized as a de facto standard for CMOS may fail when considering devices with different characteristics.

Fig. 2 .

 2 Fig. 2. Possible PGs for different logic primitives.

Fig. 4 .

 4 Fig. 4. Multi-Function Pass Diagram node mapping with different technologies.

11 if 16 if 17 M 19 M

 11161719 SharedNodes(P , Q) then 12 C M .append(Q) |C E | > 0 then ← ApplyBoolSub(P , C E , G) 18 else if |C M | > 0 then ← MergeIsomorphic(P, C M ) 20 OM F P D.append(M ) 21 end

Figure 3 -

 3 (b) and 3-(c) show the results of the optimization procedures described above applied on the MFPD obtained through the build function (Figure 3-(a)).

Fig. 6 .

 6 Fig.6. Average device count after synthesis and mapping. Graphene (left), Ambipolar Si-NWs (center), MOSFET PTL (right).

Fig. 7 .

 7 Fig. 7. Average device count after synthesis and mapping. Graphene (left), Ambipolar Si-NWs (center), MOSFET PTL (right).

Fig. 8 .

 8 Fig. 8. Normalized PDP vs transition time.

Fig. 9 .

 9 Fig. 9. Normalized dynamic power vs. transition time.

Table 1 .

 1 PLA table of function[START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF]

Table 2 .

 2 MFPD reduction rule efficiency.

						PI PO	I	Number of nodes
								w/o opt w/ opt Savings %
				sao2		10	4	58	229	152		33.62
				o64		130	1	65		65	65		-
				5xp1		7 10	75	161	111		31.06
				c8		28 18	79	156	108		30.77
				duke2	22 29	87	401	287		28.43
				apex1	45 45	206	921	677		26.49
				misex1	8	7	32		67	31		53.73
				misex2	25 18	29	101	75		25.74
				b12		15	9	431	1007	579		42.50
				k2		45 45	936	3791	2103		44.53
				bigkey	486 421 6151	19054 10771		43.47
				s13207.1 700 790 10987	53868 33005		38.73
								Total	79821 47964 Avg. 39.91
	Avg. # of nodes Avg. # of nodes	10 0 10 1 10 2 10 3 10 4 10 5 10 0 10 1 10 2 10 3 10 4 10 5	2521.5 2521.5	141474.42 141474.42	61995.67 61995.67	3997 3997	8695.75 8695.75	Avg. depth (# of gates) Avg. depth (# of gates)	1 10 100 1 10 100	22.83 22.83	126.75 126.75	121.33 121.33	5.25 5.25	10.17 10.17
			AIG BBDD BDD MFPD PD AIG BBDD BDD MFPD PD			AIG BBDD BDD MFPD PD AIG BBDD BDD MFPD PD

Fig. 5. Binary MFPDs efficiency w.r.t. PDs, BDDs, BBDDs and AIGs. Average number of nodes (left), average depth (right).


Christophe N Magnan

Cécile Capponi

Franc ¸ois Denis

A Protocol to Detect Local Affinities Involved in Proteins Distant Interactions

The tridimensional structure of a protein is constrained or stabilized by some local interactions between distant residues of the protein, such as disulfide bonds, electrostatic interactions, hydrogen links, Wan Der Waals forces, etc. The correct prediction of such contacts should be an important step towards the whole challenge of tridimensional structure prediction. The in silico prediction of the disulfide connectivity has been widely studied: most results were based on few amino-acids around bonded and non-bonded cysteines, which we call local environments of bonded residues. In order to evaluate the impact of such local information onto residue pairing, we propose a machine learning based protocol, independent from the type of contact, to detect affinities between local environments which would contribute to residues pairing. This protocol requires that learning methods are able to learn from examples corrupted by class-conditional classification noise. To this end, we propose an adapted version of the perceptron algorithm. Finally, we experiment our protocol with this algorithm on proteins that feature disulfide or salt bridges. The results show that local environments contribute to the formation of salt bridges. As a by-product, these results prove the relevance of our protocol. However, results on disulfide bridges are not significantly positive. There can be two explanations: the class of linear functions used by the perceptron algorithm is not enough expressive to detect this information, or cysteines local environments do not contribute significantly to residues pairing.

Introduction

Since many years, biology provides computer science with crucial problems. In particular, the prediction of proteins tridimensional (3D) structure starting from primary amino acids sequence is a current challenge for both biologists and computer-scientists. The 3D structure of proteins almost determines their functions. About 5 millions of proteins primary sequences are available in different databases, whereas approximatively only 40.000 3D structures are known. Moreover, determining 3D structures experimentally is a long, expensive and unreliable task. It is the reason why many researchers work at developing automatic learning methods for predicting the structure of new proteins from known, experimentally designed structures.

Different bioinformatics ways to determine proteins structures have been proposed. The most widespread method consists in predicting different structural elements and long-range contacts, then to propose the set of possible 3D structures matching these predictions. The prediction of the secondary (2D) structure, an intermediary structure between the amino-acids sequence and the 3D structure, have received considerable attention from researchers. β-sheets prediction [START_REF] Hutchinson | Determinants of strand register in antiparallel β-sheets of proteins[END_REF][START_REF] Merkel | Sidechain interactions in parallel β-sheets: the energetics of crossstrand pairings[END_REF][START_REF] Steward | Prediction of strand pairing in antiparallel and parallel β-sheets using information theory[END_REF][START_REF] Sen | Statistical analysis of pair-wise compatibility of spatially nearest neighbor and adjacent residues in α-helix and β-strands: Application to a minimal model for secondary structure prediction[END_REF][START_REF] Cheng | Three-stage prediction of protein βsheets by neural networks, alignments and graph algorithms[END_REF] or α-helix [START_REF] Zhang | Prediction of the helix/strand content of globular proteins based on their primary sequences[END_REF][START_REF] Sen | Statistical analysis of pair-wise compatibility of spatially nearest neighbor and adjacent residues in α-helix and β-strands: Application to a minimal model for secondary structure prediction[END_REF][START_REF] Ruan | Highly accurate and consistent method for prediction of helix and strand content from primary protein sequences[END_REF] are examples of secondary structure elements.

Apart 2D structures, some punctual interactions between distant residues of the primary sequence of a protein, are also of interest, even if they are sometimes considered as a consequence of the 3D conformation rather than a cause. Among them, disulfide bridges have been widely studied.

The prediction of such covalent bonds from primary sequences is a two-stages process: (i) prediction of the oxidization state of cysteines; (ii) prediction of the disulfide connectivity: which cysteine is bonded with such other given oxidized cysteine?

The first stage has been widely studied [START_REF] Fariselli | Role of evolutionary information in predicting the disulfide-bonding state of cysteine in proteins[END_REF][START_REF] Fiser | Predicting the oxidation state of cysteines by multiple sequence alignment[END_REF][START_REF] Mucchielli-Giorgi | Predicting the disulfide bonding state of cysteines using protein descriptors[END_REF][START_REF] Martelli | Prediction of the disulfide bonding state of cysteines in proteins with hidden neural networks[END_REF][START_REF] Martelli | Prediction of the disulfide-bonding state of cysteines in proteins at 88% accuracy[END_REF][START_REF] Frasconi | A two-stage svm architecture for predicting the disulfide bonding state of cysteines[END_REF][START_REF] Ceroni | Predicting the disulfide bonding state of cysteines with combinations of kernel machines[END_REF][START_REF] Song | Prediction of the disulfide-bonding state of cysteines in proteins based on dipeptide composition[END_REF][START_REF] Ceroni | Disulfind: a disulfide bonding state and cysteine connectivity prediction server[END_REF][START_REF] Cheng | Large-scale prediction of disulphide bridges using kernel methods, two-dimensional recursive neural networks, and weighted graph matching[END_REF], leading to fairly good performances: about 90% of correct predictions. Meantime, some methods have been proposed for the prediction of the correct connectivity [START_REF] Fariselli | Prediction of disulfide connectivity in proteins[END_REF][START_REF] Fariselli | A neural networkbased method for predicting the disulfide connectivity in proteins[END_REF][START_REF] Vullo | A recursive connectionist approach for predicting disulfide connectivity in proteins[END_REF][START_REF] Vullo | Disulfide connectivity prediction using recursive neural networks and evolutionary information[END_REF][START_REF] Ferrè | Disulfide connectivity prediction using secondary structure information and diresidue frequencies[END_REF][START_REF] Zhao | Cysteine separations profiles on protein sequences infer disulfide connectivity[END_REF][START_REF] Baldi | Large-scale prediction of disulphide bond connectivity[END_REF][START_REF] Ceroni | Disulfind: a disulfide bonding state and cysteine connectivity prediction server[END_REF][START_REF] Cheng | Large-scale prediction of disulphide bridges using kernel methods, two-dimensional recursive neural networks, and weighted graph matching[END_REF]. However, none have reached 63% of correct connectivity despite their strong biological, theoretical, and algorithmic foundations. Moreover, the prediction results are non stable. Actually, most of these methods use the local environment around cysteines to predict their pairing (i.e. the 5 ou 6 amino-acids that range on each side of each cysteine in the primary sequence). Hence, in order to improve automatic methods, it is worthwhile to wonder which information is actually useful for predicting the disulfide connectivity. Basically, are local environments enough? Some biochemists and structural biologists would answer yes, while some other would definitely argue that the disulfide connectivity is a consequence of the definite proteins folding, thus depending on many other factors: they consider than local environments do not carry any information for disulfide connectivity.

In order to evaluate the impact of local environments of cysteines onto disulfide connectivity, we study an experimental protocol aiming at revealing a potential affinity between oxidized cysteines for further bonding. Our hypothesis is that, before the protein folds, some couples of cysteines are more likely to bond than others, given the aminoacids of their primary sequence neighborhood. The best results of past studies were obtained when considering only the 5 ou 6 closest amino-acids of a cysteine in the primary sequence. Our aim is to point out an hypothetic affinity between the local neihborhoods of cysteines. Such an affinity should then be involved in the observed bridges, while being independent from the secondary structure (α-helix and β-sheets). Assuming that such an affinity exists, we suppose that we can detect, extract and evaluate it with machine learning methods launched on observed disulfide connectivity. More generally, we realize this study among several categories of contacts among residues which may driven by some local information.

We thus propose a formalization of the affinity between residues: we focus on a protocol for learning a function representing this affinity from labeled examples available in databases. Starting from machine learning considerations, the main idea of our proposal is to assume that actual bonded residues (positive examples) are not the only examples of high propensity residue pairs: some non-bonded cysteines might also be propitious to form a disulfide bridge according to their neighborhood while some other information does not allow them to actually bond. In previous works, observed bonded residues are considered as positive examples, while non-bonded residues are definitely negative examples: pairs that cannot contact. We argue that our hypothesis may be used for improving usual machine learning methods for predicting residue connectivity. Indeed in a previous work [START_REF] Magnan | Asymmetrical semi-supervised learning and prediction of disulfide connectivity in proteins[END_REF], we considered non-bonded residues as unlabeled examples (neither positive nor negative): we then obtained better predictive performances, using a simple naive bayesian classifier, than when nonbonded residues where labeled as negative examples.

In these preliminary works, we considered that there exists an affinity function g, defined on pairs of local environments, which can only take two values: 1 means a high affinity between both environments, while 0 reveals a low affinity. We postulate that pairs with high affinity are more likely to bound than pairs with low affinity. Thus, bounded and unbounded pairs available in proteins databases can be considered as examples of pairs labeled with g. Furthermore, these pairs might have been corrupted with classification noise: not all unbonded pairs (resp. bonded pairs) have low (resp. high) affinity. Such a model of noise have already been studied in the machine learning litterature. It is refered to as class-conditional classification noise (CCCN), a generalisation of the well-known uniform classification noise (CN). If our base hypothesis is correct, a learning algorithm that is capable of learning from data corrupted by CCCN noise, should also be able to learn the affinity function g from bonded and unbonded pairs of cysteines issued from the proteins databases. Then we should be able to prove that local environments carry some information on the connectivity by checking that pairs with high affinity are more likely to be bonded than pairs with low affinity.

Section 2 is concerned with the presentation and the formal modelling of the biological problem in terms of machine learning methods. Section 3 concerns the algorithms that we propose to learn the affinity function, which are proven to be efficient in some noisy contexts. Section 4 reports some of the numerous experiments we performed: a discussion on the presented results is worthwhile and we hope it will give rise to advices from the whole community of structural biologists and computer scientists.

Affinity of protein distant interactions

Disulfide bridges and salt bridges

A protein may be represented by its primary structure -a sequence of amino-acids-from which a tridimensional structure is gathered. Theoretically, a protein could have many conformations. However, one structure seems to be privileged in a given biological context: the active form of the protein [START_REF] Anfinsen | Principles that govern the folding of protein chains[END_REF]. Nowadays, some interactions are known that contribute to protein stability, such as: hydrogen links, electrostatic interactions, covalent bonds, Wan Der Waals forces. As a matter of fact, the prediction of such interactions should be of great help for the prediction of the structure from the sequence. We are particularly interested by the prediction of affinity between cysteines to bond, making up disulfide bridges. However, the protocol we study can be applied on other contacts such as salt bridges.

Disulfide bridges are involved in the 3D conformation of a protein as covalent bonds between two oxidized cysteines (amino-acid C). Such a physical interaction between two residues is a strong, well-conserved link, thus a strong constraint for the stability of the protein structure. Experimental ways of determining them on proteins, through RMN, Xray crystallography or site-directed mutagenesis, is a long and expensive process.

Salt bridges are relatively weak ionic hydrogen bonds made up of the interaction between two charged residues. As disulfide bonds, they contribute to the stability of the structure. They involve two residues of the proteins, so are of great interest in our protocol since we study the affinity of two residues for interacting, based on their neighborhood.

A model of affinity between residues

We present a model and a protocol to answer the question of a local affinity implied in the formation of local interactions between two distant residues of a protein primary structure. We present the protocol through disulfide bonds, but other bonds are also directly concerned as long as the distant contacts involve few residues.

Modeling the data

The primary structure of a protein p can be considered as a word w of Σ * where Σ represents the set of twenty amino acids or any other similar alphabet. Let P ⊂ Σ * be the set of proteins containing an even number of cysteines involved in disulfide bridges (oxidized cysteines). Let P l ⊂ P be the proteins with 2l cysteines involved in disulfide bridges.

Let G be the set of non-oriented graphs where nodes have degree 1. For a protein p ∈ P, nodes of the associate graph in G represent oxidized cysteines of p, and an edge represent a disulfide bond between two cysteines of p. Let φ : P → G be a function which associates a graph in G (the disulfide connectivity) to a protein in P. Then, our aim is to approximate the function φ with the highest precision, using examples issued from experiments.

To do so, many authors use local environment of cysteines, i.e. amino acids located around the cysteines (figure 1). Usually, segments centered on cysteines of size 2r+1 are considered. Let P be a probability distribution over P and let Ω r =Σ 2r+1 be the set of protein segments of size 2r+1. The elements of Ω r are local environments of cysteines, also called windows: a sequence of residues whose center is an oxidized cysteine. On the figure 1, the local environments are w 1 =LP OCM T N , w 2 =DN HCEIS, w 3 =EQACP HI, w 4 =DSRCN T E. For w, w ′ ∈ Ω r , let:

• P (w) be the probability that w is a local environment of a cysteine into a protein p ∈ P

• P (w, w ′ ) be the probability that w and w ′ are distinct local environments of a cysteine into a protein p ∈ P

• P (w, w ′ |l) be the probability that w and w ′ are distinct local environments of a cysteine into a protein p ∈ P l

• P (B(w, w ′ )|w, w ′ , l) be the probability that w and w ′ are bonded knowing that there are distinct local environments of cysteines into a protein p ∈ P l .

Modeling the impact of local environment on bonds

As pointed out in the introduction, past results of automatic methods for the prediction of disulfide bridges based on the proteins sequence are not satisfactory. The error rate remains high (about 40%) while the results are not stable (removing few proteins that are known to be hard to model seems to boost the overall process towards better efficiency). Most of these methods relies upon the local environments of cysteines, namely the environments w modeled above. The aim of our work is to answer the question: is the local information involved in the formation of disulfide bonds? Is there any information in the closest neighborhood of the cysteines that would help to predict their bonding during the protein folding process?

In order to answer that question, an affinity measure among cysteines based on their local environment must be highlighted through a functional represesention. The affinity between cysteines must be considered as a necessary, but not sufficient, condition for their actual physical distant interactions. We assume that if such a function exists, then there is a way to learn it from examples. In this section, we draw a model of affinity as well as a protocol to learn it from known disulfide bridges.

Let p be a protein with l bridges (2l involved cysteines). If there is no local information for pairing cysteines into bridges, then there is 2l-1 pairing possibilities for each cysteine, so

P (B(w, w ′ )|w, w ′ , l)= 1 2l-1 . Reciprocally if P (B(w, w ′ )|w, w ′ , l)= 1 2l-1
, there is no local information since the actual pairing does not depend on w nor on w ′ . Our solution is to assume the existence of an affinity function g : Ω r x Ω r → Y such as:

g(w 1 , w 2 ) = g(w ′ 1 , w ′ 2 ) ⇒ P (B(w 1 , w 2 )|w 1 , w 2 , l) = P (B(w ′ 1 , w ′ 2 )|w ′ 1 , w ′ 2 , l) and y < y ′ ⇒ P (B(w 1 , w 2 )|g(w 1 , w 2 ) = y) < P (B(w ′ 1 , w ′ 2 )|g(w ′ 1 , w ′ 2 ) = y ′ ) (y, y ′ ∈ Y ).
The simplest situation is Y = {0, 1} (Figure 2 : 0 means low affinity between local environments, whereas 1 means a high affinity). In such a case, pairs of windows are partitioned into two classes, corresponding to two affinity levels and

P (B(w, w ′ )|w, w ′ , l) = P (B(w, w ′ )|g(w, w ′ ), l) = α l 1 if g(w, w ′ ) = 1 α l 0 if g(w, w ′ ) = 0
Assuming that g exists and plays a role in the interaction, then we must have α l 1 significantly higher than α l 0 . In other words, there are more bonded cysteines when there is a high affinity between their local environments w and w ′ (g(w, w ′ )=1) than when there is a low affinity (g(w, w ′ )=0). The observed bonded and unbonded pairs of local environments centered on oxidized cysteines are then indirect information on g since our model does not exclude that pairs with a high affinity level could be unbonded, neither that a bridge can hold among a pair of cysteines for which g=0.

Bonded and unbonded cysteines as noisy observations of g

From a machine learning point of view, it is an interesting learning context because the observed classes (bonded or non-bonded) of observed examples (local environments of cysteines) do not carry direct information about the affinity function g. This is pictured on figure 3: some pairs of environment are labeled "bonded" while their affinity is 1, and vice-versa. Such an phenomenon is quite usual in machine learning: we interpret these mislabeled pairs as noisy labels with regards to the function g to learn. More precisely, using the previous expression of P (B(w, w ′ )|g(w, w ′ ), l), one can observe that pairs such that g = 1 correspond to the observation of a bridge with noise η + = 1 -α l 1 , and, symetrically, pairs such that g = 0 correspond to a nonbonded pairs with noise η -= α l 0 . One could observe that the noise is somehow a measure of mislabelling rates.

On the one hand, this kind of noise is a generalization of the well-known uniform classification noise (CN) since it does not make the assumption that positive and negative examples are corrupted by the same noise process (noise rates η + and η -can be different). On the other hand, it is a particular case of constant-partition classification noise (CPCN) because there is a fixed number of classes in the space of attributes descriptions to separate (namely two classes: g = 0 and g = 1). Such a noise has been studied in [START_REF] Ralaivola | Cn = cpcn[END_REF][START_REF] Denis | Efficient learning of naive bayes classifiers under class-conditional classification noise[END_REF].

Setting up the protocol to learn g

If a local information exists (i.e. if local environments of cysteines contribute to their pairing), and if it can be represented by a function in a concept class learnable in CCCN context, then we should be able to detect, extract and evaluate it. Our study thus concerns the setting up, and the test, of a protocol for learning the hypothetic affinity function from proteins where disulfide bridges are known.

In [START_REF] Denis | Efficient learning of naive bayes classifiers under class-conditional classification noise[END_REF], we show that naive Bayes classifiers are identifiable from examples corrupted by a CCCN noise, and we design an efficient algorithm for learning product distributions in this context. Nevertheless, this algorithm assumes the independence of attributes describing data, which does not hold in the case of protein folding. In [START_REF] Ralaivola | Cn = cpcn[END_REF] CCCNlearnable concept classes are proved to be CN-learnable concept classes, in the PAC learning framework. Such a result is of major importance for the local affinity detection protocol we propose: it allows us to search in all CNlearnable concept classes in the PAC framework.

In the section, we propose an efficient algorithm to learn one of these concept classes: the linear threshold functions. This algorithm is a generalization of the perceptron algorithm. [START_REF] Bylander | Learning linear threshold functions in the presence of classification noise[END_REF][START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF] sketched two adaptations of it in the CN learning context: we generalize the work of [START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF] in the CCCN context. We thus propose a perceptron in order to apply our protocol on real datasets for disulfide and salt bridges (see Section 4).

A CCCN-learning adaptation of the perceptron Algorithm

The previous section reveals that if an affinity exists between local environments of cysteines, and if it can be represented by a function in a concept class learnable with class-conditional classification noise (CCCN), then it can be learned from examples issued from databases as PDB. In [START_REF] Ralaivola | Cn = cpcn[END_REF], we prove that the concept classes learnable with uniform classification noise (CN) are the same than the concept classes learnable from CCCN noise. As a consequence, linear threshold functions are learnable in CCCN context.

In order to experiment the protocol proposed (section 2), this section shows that the perceptron algorithm can be adapted for data corrupted by a CCCN noise. This algorithm generalizes the algorithms proposed in [START_REF] Bylander | Learning linear threshold functions in the presence of classification noise[END_REF][START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF] since it can deal with data corrupted by CCCN noise therefore CN.

Linear Threshold Functions

Let S = {(x 1 , l(x 1 )), ..., (x n , l(x n ))} be a set of labeled examples 1 (for instance, the set of all pairs of local envi- 1 We use annotations 1 or + for bonded pairs -positive examples -, and either -1 orfor unbonded pairs -negative examples -.

Algorithm 1 Sketch of the perceptron algorithm

Require: S = {(x 1 , l(x 1 )), (x 2 , l(x 2 )), ..., (x n , l(x n ))} w = -→ 0 while ∃(x, l(x)) ∈ S such that w • l(x)x < 0 do Let x upd be a vector such that w * • x upd > 0 and w • x upd < 0 w = w + x upd end while

Ensure:

w such that ∀(x, l(x)) ∈ S, w • l(x)x > 0 ronments of cysteines), such that x i ∈ R m (
• x| = min x∈S w * • l(x)x = σ (x = x ||x|| ).
In this context, our first purpose is to infer, from a linearly separable set S, an hypothesis w such that w separates positive and negative examples of S: ∀(x, 1) ∈ S, w • x>0 and ∀(x, -1) ∈ S, w • x<0, or ∀(x, l(x)) ∈ S, w • l(x)x>0.

Perceptron Algorithm

The perceptron algorithm [START_REF] Rosenblatt | Principles of neurodynamics[END_REF] is an iterative method for infering a hyperplane w passing by origin, that separates a linearly separable dataset S. A sketch of this algorithm is given on algorithm 1.

In the usual form, x upd = l(x B )x B , where x B is an example wrongly classified by the current hyperplane w, and xB = x B ||x B || . This algorithm requires at most 1 σ 2 iterations, where σ is the maximal margin among hyperplanes separating S [START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF]. It is exponential in the worst case, yet rather efficient in most real problems.

Others possibilities exist for choosing x upd , for instance l(x B )x B , or any other colinear vector such as the average of the misclassified examples, or its normalized sum. The convergence property holds whenever the selected x upd is wrongly classified by w and not too close from w * :

cos(w * • x upd ) ≥ σ. Let us notice that, if ∀x ∈ S, |cos(w * , x)| ≥ σ, then cos(w * , l(x B )x B ) ≥ σ).

Experimentations

We tested the protocol presented in section 2 on two datasets featuring disulfide and salt bridges. We applied the algorithm 2 (section 3) in order to learn a local affinity function supposed to be involved in the pairing of residues.

Protocol

Datasets

We ran the protocol over two proteins datasets featuring proteins which contains from two to five bonds:

1. the first dataset contains experimentally observed disulfide bridges in proteins; it is known as SPX [START_REF] Baldi | Large-scale prediction of disulphide bond connectivity[END_REF][START_REF] Cheng | Large-scale prediction of disulphide bridges using kernel methods, two-dimensional recursive neural networks, and weighted graph matching[END_REF], featuring 1676 disulfide bridges within 567 proteins (Table 1). The homology rate of proteins of SPX is smaller than 30%.

2. The second dataset compiles 1836 intern salt bridges observed in 570 proteins (Table 2); we call it G3D, for it was created from PDB [START_REF] Berman | The Protein Data Bank[END_REF] by the ACI GENOTO3D consortium, a french group working on the prediction of the 3D structure of proteins. The homology rate of proteins of G3D is smaller than 25%.

For both kinds of bonds, we distinguish the study according to the number of bonds, since the noise rates induced by proteins containing k bridges are different from the noise rates induced by proteins containing l = k bridges (section 2.2.3). Indeed, l(2l -1) pairs of cysteines could be formed within a protein containing 2l oxidized cysteines, but only l pairs are actually bonded while 2l(l -1) remain unbonded.

Coding of local environments pairs

From a protein p l containing l bonds (2l oxidized cysteines), we extract l(2l -1) pairs of local environments centered on a cysteine, with radius r (i.e. windows of size 2r + 1). We set r to 6 (i.e. local environments of size 13, including the central cysteine, because it corresponds to the best results we and other authors have obtained so far). For any pair (w i , w j ) of p l local environments, we extract 169 residue pairs (A i , A j ) (i, j ∈ {1, ..., 13}) where A i ∈ w i and A j ∈ w j . Each pair (w i , w j ) is modeled with a vector of R m , where m is the number of ordered pairs of residues within the alphabet Σ, and where each coordinate is the number of times a pair is observed in (w i , w j ). The alphabet Σ contains a symbol for each amino-acid, and a symbol X which denotes any unknown amino-acid (|Σ| = 21 and m = 231) . The coding of salt bridges is quite the same, except the central amino acid since salt bridges occur between two charged residues (Aspartic Acid (D) or Glutamic Acid (E) with Lysine (K), Arginine (R) or Histidine (H)).

Results

We launched two experiments: one for learning the affinity function involved in disulfide bridges (table 4 and figure 5), and the other for learning the affinity function involved in the salt bridges formation (table 5 and figure 6). Three criteria are reported with standard square deviations:

1. P (g=1), the probabilities that pairs of local environments have a high level of affinity (computed with linear functions infered with the perceptron algorithm), 2. P (B|g=1), the probability to observe a bond knowing that the pair is predicted to have a high level of affinity, 3. P (B|g=0) the probability to observe a bond knowing that the pair is predicted to have a low level of affinity.

Each reported result is an average of five 10-fold crossvalidations on the subset of proteins containing n bridges (2 ≤ n ≤ 5). Standard deviations are italized.

It is worthwhile to notice that, in order to ensure that the detected local information is not correlated with beta sheets or alpha helix in proteins, we launched experiments to look after (i) the ratio of residues involved both in bridges and beta sheets, (ii) the ratio of residues involved both in bridges and alpha helix, and (iii) those only involved in either disulfide or salt bridges. These experiments show that no correlation exists between the level of affinity predicted for local environments pairs and these 2D structural elements.

As discussed in section 4.3, we observe that results on salt bridges show that an affinity between local environments is learnt, whereas there is no evidence that such an affinity exists that would guide the formation of disulfide bridges.

Discussion

On one hand, results on salt bridges reveal that a clear signal is detected: there exists local information that is involved in the formation of salt bridges. That signal is quite constant along the experiments (standard deviations are small in comparison with the differences of probabilities P (B|g = 1) and P (B|g = 0)). Figure 5 shows that whatever the number of bonds is, our algorithm learns an affinity function g that always classify more observed bonds as having high affinity than having low affinity. In other words, we pointed out an affinity function between local environments of salt bridges. The detected affinities might be explained either by the ionic nature of salt bridges, which often involves the charge of their local environments, or/and by the hydrophilic property of many residues around salt bridges. Thus, the results that we obtained seem to validate our protocol for detecting an affinity function between local environments of paired residues.

On the other hand, the results on disulfide bridges pictured on figure 4, are not as clear as expected: probabilities P (B|g = 1) and P (B|g = 0) are really close to the baseline probabilities given in table 3 (especially for proteins containing 2 and 5 bridges). These results may be explained by several independent reasons.

1. Biology reality. The first insight of our results is that there might be no local information that would guide the formation of disulfide bridges during the 3D conformation of proteins. Such an explanation would be shared with many biologists and biochemists: disulfide bonds are so strong interactions (covalent links) that the propensity between their environments is not enough determining for guiding actual bonds.

2. Data sparsity. The perceptron algorithm is known to fail on high dimensional spaces, as here where vectors are of size 231 and many values are null, because it does not optimize the margin between the infered hyperplane and the examples. In order to estimate the impact of sparsity on our experiments, we used hyperplanes infered by this algorithm, for relabelling the learning data. A soft-margin algorithm has then been launched on these re-labelled dataset in order to optimize the margin. However, no significant improvement has been observed on test data: the sparsity seems to be not responsible of the flat results.

Learning a function in the wrong concept classes.

The affinity function g that we try to learn might be not representable by a linear threshold function such as learnt by any perceptron. It might be a function of another concept class: obviously, we still have to design other algorithms adapted to CCCN noise in other concept classes.

However, this work does not allow us to known which assumption is the most probable. The case of the disulfide bridges stays an open question. In future work, we shall have to learn the affinity function g in other concept classes to check if the results are similar to those reported here.

Conclusion

These experiments validate our protocol and show that this method make possible to detect a true signal of affinity between local environments, with a good quality. Results obtained on the salt bridges (G3D) are quite relevant because they confirm that the perceptron algorithm with CCCN noise always outputs an affinity: bonded pairs are mostly classified as having a high level of affinity. The stability of the results confirms the existence of an affinity function. Consequently, we can conclude that the local environment of charged residues is involved in the formation of salt bridges.

The perceptron algorithm might not be the right one for detecting affinities of environments in forming disulfide bridges, assuming that such a phenomenon exists and is implied in the pairing of oxidized cysteines. As a consequence, we can not currently be sure that there is no local affinity contributing to the pairing of oxidized cysteines: the chosen algorithm did not detect them. Thus, other algorithm must be tested within our CCCN noise-based protocol.

Conclusions and future works

We presented a machine-learning based protocol to answer the question of the presence of local affinities that would be involved in the pairing of distant residues in proteins. We validated this protocol since we were able to learn an affinity between local environments of salt bridges. However, the same protocol has not yet indicated any impact of local environments on the formation of disulfide bonds. More generally, the protocol can be used in order to detect any affinity between pairs of local environments residues.

In a machine learning point of view, this work is a success for it proves that it is crucial to theoretically study other algorithms fitting the CCCN context. We expect finding an algorithm for learning another concept class, that would be adapted to the highlighting of an affinity between local environments of residues to form bonds.

The presented protocol initiates the state of the art for the question of the existence of local affinities involved in local interactions. Yet many studies have to be done using this protocol for surrounding this question. We now hope that several biologists and computer scientists will help us to prove an answer, whatever it could be.

Figure 1 .

 1 Figure 1. A piece of a sequence of aminoacids, with two disulfide bonds between pairs of oxidized cysteines. Predicting disulfide bonds could be achieved through the function φ that computes the correct disulfide connectivity of a protein. There are four local environments, one for each cysteine; here, each local environment is of size 7 (3 aminoacids each side, and the cysteine itself).

Figure 2 .

 2 Figure 2. Representation of a two-levels affinity function g in function of the values of g * = P (B(w, w ′ )|w, w ′ , l). The pairs (w, w ′ ) of local environments are ordered by the value of g * .

Figure 3 .

 3 Figure 3. Schematic repartition of local environments pairs for both values of g. Bonded pairs are grouped in set B.

Figure 5 .

 5 Figure 5. Graphical view of table 4.

Figure 6 .

 6 Figure 6. Graphical view of table 5.

  m the size of the descriptive attributes space) and l(x i ) ∈ {-1, 1}. S is linearly separable by an hyperplane H if the positive and negative examples of S are separated by H. We refer to a linearly separable set S if S is separable by an hyperplane which passes by the origin 2 . Such a hyperplane H is identified by a vector w

* ∈ R m such that ||w * || = 1 and ∀x ∈ R m , x ∈ H if and only if x • w * = 0. We say that w * separates examples in S with margin σ if min x∈S |cos(w * , x)| = min x∈S |w *

Table 1 . Statistics of SPX (disulfide bridges)

 1

		Nb of Proteins Total nb. of bridges
	2 salt bridges	182	364
	3 salt bridges	166	498
	4 salt bridges	136	544
	5 salt bridges	86	430

Table 2 . Statistics of G3D (salt bridges)

 2

Table 3 . Probabilities to observe a bonded pair in a protein containing

 3

	Bonds	P(g=1)	P(B|g=1)	P(B|g=0)
	2	0.622	0.338	0.325
		± 0.088	± 0.009	± 0.018
	3	0.436	0.228	0.179
		± 0.031	± 0.005	± 0.002
	4	0.608	0.154	0.124
		± 0.087	± 0.003	± 0.008
	5	0.528	0.116	0.105
		± 0.051	± 0.005	± 0.005

2n (2 ≤ n ≤ 5) bonded residues = 1/(2n -1)

Table 4 . Characteristics of the affinity func- tions g learned by the CCCN-perceptron al- gorithm on SPX.

 4

	Bonds	P(g=1)	P(B|g=1)	P(B|g=0)
	2	0.649	0.381	0.246
		± 0.037	± 0.009	± 0.012
	3	0.485	0.243	0.160
		± 0.068	± 0.005	± 0.007
	4	0.482	0.174	0.114
		± 0.061	± 0.005	± 0.003
	5	0.593	0.129	0.084
		± 0.047	± 0.003	± 0.005

Table 5 . Characteristics of the affinity func- tions g learned by the CCCN-perceptron al- gorithm on G3D.

 5

One may transform any set S, linearly separable, by an hyperplane H that does not cross the origin, into another set S ′ that is linearly separable by an hyperplane H ′ crossing the origin.

Classification noise

Observed classes of the examples may be corrupted by a noise process: the assigned class for some examples may be wrong, for any reason. The standard perceptron algorithm can not be applied, for it is no more possible to know whether an example is misclassified by w. The most studied noise process is the uniform classification noise (CN), where the labels of examples are supposed to be independently flipped with a constant noise rate η < 0.5. Two adaptations of the perceptron algorithm in a CN context have been proposed in [START_REF] Bylander | Learning linear threshold functions in the presence of classification noise[END_REF][START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF]. The second one presents a direct analysis which computes, when η is known, an estimated value of l(x B )x B where x B are misclassified examples 3 . In order to select a good hypothesis when the noise rate is unknown, it is usual to scan the rate within [0, 0.5[ for selecting the hypothesis that leads to the smallest error.

We generalize this noise process by assuming that the noise rate over positive examples is not the same than the noise rate over negative examples, i.e. η + and η -∈ [0, 1], η + + η -< 1 to avoid any ambiguity. Introduced in [START_REF] Ralaivola | Cn = cpcn[END_REF], this new kind of noise was refered to as classconditional classification noise (CCCN). The next section briefly presents an adaptation of the perceptron algorithm within the CCCN-learning framework.

CCCN-Perceptron Algorithm

This section briefly presents an adaptation of the perceptron algorithm when data is known to be corrupted by CCCN noise, which generalizes the perceptron of [START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF]. Only the differences with [START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF] are reported, yet proofs are drastically shortened in order to stay in the scope of this paper. For more details, the reader is adviced to refer to [START_REF] Blum | A polynomial-time algorithm for learning noisy linear threshold functions[END_REF][START_REF] Ralaivola | Cn = cpcn[END_REF].

Known noise rates: η

} be a non-noisy learning dataset. The hyperplane w * splits S in two sets S + and S -. S + is the set of positive examples of S (w * •x > 0), and S -is the set of negative examples of S (w * • x < 0). In the same way, at each step of the iteration, the current perceptron hyperplane w splits S in two sets S + and S -. That second partition of S is the only one that is observed during the process. When examples of S are corrupted by CCCN noise, we can then estimate the sum of the examples of each of the four parts depicted on figure 4:

Then, we can estimate l(x B )x B =Sum[S

where esperances E[.] are considered relatively to the observations we could have of S with the same CCCN noisy process. Using Sum[] to denote the estimations:

After inversion of the system, and assuming η + + η -= 1, we obtain:

With the same demonstration, we obtain:

, we finally compute an estimation of the vector E[x upd ]= l(x B )x B , which only depends on the observations, η + and η -. We thus propose the algorithm 2 as an adaptation of the perceptron algorithm when S is corrupted with CCCN and when the noise rates are known.

Noise rates η + and η -unknown

When noise rates η + and η -are unknown, it is necessary to scan the interval [0, 1] for the values of η + and η -with a step s ≥ 1 n where n = |S|: algorithm 2 is launched for each pair value of the noise rate for computing an hypothesis. However, the principle of empirical risk minimization does not necessarily hold in CCCN context (see [START_REF] Denis | Efficient learning of naive bayes classifiers under class-conditional classification noise[END_REF]).

We thus propose a consistent criterion to select an hyperplane when data is corrupted by a noise CCCN (proof is not given here). This criterion is based on two other criteria independently inconsistent, but which can be laid out to build a consistent whole criterion. The first criterion selects the noise rate associated with the hypothesis w computed within algorithm 2, that minimizes the norm of x upd (computed with w) 4 . The second criterion selects the noise rate that minimizes the sum of the differences between their values (given to the algorithm) and the value of the same parameters computed on S with the hypothesis w within algorithm 2. The main idea of this criterion is that the algorithm must compute, with the real noise rates in input, an hypothesis w for which the computed values of noise rates on S are close to the real values.

Separately, criteria are inconsistent. However we have shown that the only hyperplane that minimizes both criteria is w * . Then, looking for the hyperplanes that minimize both criteria and selecting the first appearing in these hyperplanes, is a consistent way for selecting a fair hypothesis. 4 x upd represents an estimate of the sum of examples that are misclassified by hyperplane w.

Nb of