extfieldsofstudy:
Computer Science
Mathematics

text:
Generating Complete and Finite Test Suite for ioco: Is It Possible?

Testing from Input/Output Transition Systems has been intensely investigated. The conformance between the implementation and the specification is often determined by the so-called ioco-relation. However, generating tests for ioco is usually hindered by the problem of conflicts between inputs and outputs. Moreover, the generation is mainly based on nondeterministic methods, which may deliver complete test suites but require an unbounded number of executions. In this paper, we investigate whether it is possible to construct a finite test suite which is complete in a predefined fault domain for the classical ioco relation even in the presence of input/output conflicts. We demonstrate that it is possible under certain assumptions about the specification and implementation, by proposing a method for complete test generation, based on a traditional method developed for FSM.

Introduction
Testing from Input/Output Transition System (IOTS) has received great attention from academy and industry alike. The main research goal is to devise a theoretically sound testing framework when the behavior of an Implementation Under Test (IUT) is specified as the IOTS model. It is assumed that the tester controls when inputs are applied, while the IUT autonomously controls when, and if, outputs are produced. The IUT's autonomy causes issues in testing. Simply stated, the interaction between the IUT and the tester should be assumed to be asynchronous, since otherwise the tester should have the ability to block the IUT when the latter is ready to produce output but the former has input to be sent. Most approaches based on the so-called ioco conformance relation do not offer sound solutions to the problem of conflicts between inputs and outputs. In particular, the proposal [15] for input-enabled testers addressing the conflicts lead to uncontrollable tests, while it is widely agreed that only controllable tests, which avoid any choice between inputs or between input and output, should be used. The approaches for test purpose driven test generation from the IOTS implemented in tools such as TGV [8] and TorX [16], as well as in Uppaal Tron which also accepts the IOTS, face the same problem of treating input/output conflicts.
These issues have drawn significant attention of the testing community, e.g., [1,6,7,11], and have been dealt with by allowing implicitly or explicitly the presence of channels, e.g., FIFO queues, between the IUT and tester [6,7,17]. However, queues impose a hard burden on the tester, since the communication is now distorted by possible delay in the transmission of messages via queues. In the extreme case, queues render some important testing problems undecidable [4,5]. The issue is caused by the conflict between input and output enabled in the same state; while the IUT should be ready to receive input, it may choose to produce an output, blocking or ignoring incoming input. It has been shown that when all the states have either inputs or outputs, but not both, in the so-called Mealy IOTS, such problems do not arise [12].
Apart for the problem of input/output conflicts, the question of generating complete and finite test suite from IOTS w.r.t. the ioco relation remains open. The test generation method which is most referred in the literature relies on non-deterministic choice between: (1) stopping testing; (2) applying a randomly chosen input; or (3) checking for outputs [14]. The problem with this approach is that, although completeness is guaranteed in some theoretical sense, the practical application of this method is problematic. It requires that the process be repeated an undetermined number of times, since there is no indication of when the completeness has been achieved and thus the process can stop.
On the other hand, generation methods from Finite State Machines (FSM) approach the problem of test completeness by explicitly stating a set of faulty (mutant) FSMs, called a fault domain, which model potential faults of the IUT; then, a test suite is generated that targets each faulty FSM. Its completeness implies that each IUT possessing the modelled faults will be detected by the test suite. The existing methods for complete test generation are applicable not only to minimal deterministic machines, as the early methods [2,3,18], but also to nondeterministic FSMs [10]. This motivated a previous attempt to rephrase FSM methods for checking experiments to the IOTS model [13]. In particular, an analogue of the Harmonized State Identifier Method (HSI-method) was elaborated there for the trace equivalence relation between the specification and implementation IOTSs. The input/output conflicts were addressed by assuming that the tester detecting (using some means) them will just try to repeatedly re-execute the expected trace to verify if it can be generated by the IUT.
In this paper, we investigate whether it is possible to construct a finite test suite for a given IOTS specification which is complete in a predefined fault domain for the classical ioco relation even in the presence of input/output conflicts. Our solution to the latter is based on the assumption that any IUT in a fault domain resolves each such conflict in favor of inputs; that is, we assume that the IUT is eager to process inputs and, whenever it is in a state where it can either receive an input or produce an output, it will produce an output only if no input is available. We demonstrate this by elaborating a test generation method inspired by the HSI method [19], generalizing and adapting its concepts to the realm of IOTS. We illustrate the method with a running example. This remainder of this paper is organized as follows. In Section 2, we introduce the main concepts of IOTS and test cases. In Section 3, we present the generation method, and demonstrate that the obtained test suite is a complete for a given fault domain. Finally, in Section 4, we conclude the paper and point to future work.
2 Input/output transition system and test cases 2.1 Input/output transition system and related definitions We use input/output transition systems (IOTS, a.k.a. input/output automata [9]) for modelling systems. Formally, an IOTS S is a quintuple (S, s 0 , I, O, h S ), where S is a finite set of states and s 0 ∈ S, is the initial state, I and O are disjoint sets of input and output actions, respectively, and h S ⊆ S × (I ∪ O) × S is the transition relation. S is deterministic if h S is a function on a subset of S × (I ∪ O), i.e., if (s, x, s ) ∈ h S and (s, x, s ) ∈ h S , then s = s . While we shall consider only deterministic IOTSs, they may have outputnondeterminism, i.e., have several outputs enabled in a state.
For IOTS S, let init S (s) denote the set of actions enabled at state s, i.e., init S (s) = {x ∈ I ∪ O | ∃s ∈ S, (s, x, s ) ∈ h S }; let inp S (s) and out S (s) denote the set of inputs and outputs, respectively, enabled at state s. Thus, inp S (s) = init S (s) ∩ I; out S (s) = init S (s) ∩ O. We omit the subscript if it is clear which IOTS is considered. A state s is a sink state if init(s) = / 0; s is an input state if inp(s) = / 0. We denote the set of input states by S in . An input state s is stable (quiescent) if init(s) ⊆ I. An input state s is a quasi-stable state if out(s) = / 0. In a quasi-stable state, there is an input/output conflict (note that the IOTS itself does not provide any mechanism for resolving such conflicts). A state is an output state if it is neither sink nor input state. Figure 1 shows an example of an IOTS, where I = {a, b} and O = {0, 1}. Input states are numbered; states 1 and 4 are stable, whereas states 2 and 3 are quasi-stable.
For IOTS S, a path from state s 1 to state s n+1 is a sequence of transitions p = (s 1 , a 1 , s 2 )(s 2 , a 2 , s 3 ) . . . (s n , a n , s n+1 ), where (s i , a i , s i+1 ) ∈ h S for i = 1, . . . , n. Let ε denote the empty sequence of actions. We say that s n+1 is reachable from s 1 . IOTS S is initially-connected if each state is reachable from the initial state. A sequence u ∈ (I ∪ O) * is called a trace of S from state s 1 ∈ S if there exists path (s 1 , a 1 , s 2 )(s 2 , a 2 , s 3 ) . . . (s n , a n , s n+1 ), such that u = a 1 . . . a n . We use the usual operator after to denote the state reached after the sequence of actions (we consider only deterministic IOTS), i.e., s 1 -after-u = s n+1 ; if u is not a trace of s 1 , then s 1 -after-u = / 0. Let also Tr(T ) denote the set of traces from states in T ⊆ S. For simplicity, we denote Tr({s}) as Tr(s) and use Tr(S) to denote Tr(s 0 ). A trace u of IOTS S is completed, if s 0 -after-u is a sink state. A trace u of IOTS S is a bridge trace from input state s, if s-after-u ∈ S in and for each proper prefix w of u, s-after-w / ∈ S in . Given an IOTS S = (S, s 0 , I, O, h S ) and a state s ∈ S, let S/s denote the IOTS that differs from S in the initial state changed to s, removing states and transitions which are unreachable from s.
We use a designated symbol δ to indicate quiescence in S, that is, the absence of outputs. Quiescence can be encoded by adding self-looping δ transitions to the stable states; the resulting IOTS has the output action set O ∪ {δ }. Traces of this IOTS which end with δ are quiescent traces and traces containing δ are suspension traces. In the rest of the paper, we assume that Tr(S) includes all kinds of traces.
An IOTS T = (T,t 0 , I, O, h T ) is a submachine of the IOTS S = (S, s 0 , I, O, h S ), if T ⊆ S and h T ⊆ h S . A state s ∈ T of a submachine T of S is output-preserving if for each x ∈ O such that (s, x, s ) ∈ h S , we have that (s, x, s ) ∈ h T . The submachine T of S is output-preserving if each state which is not a sink state is output-preserving. The submachine is trivial if T is a singleton and h T = / 0. The IOTS S is progressive if it has no sink state and each cycle contains a transition labeled with input, i.e., there is no output divergence. The IOTS S is input-complete if all inputs are enabled in input states, i.e., inp(s) = / 0 implies that inp(s) = I, for each state s. The IOTS S is single-input if |inp(s)| = 1, for each input state s; it is output-complete if out(s) = O, for each output state s.
In this paper, we assume that specifications and implementations are input-complete progressive deterministic initially-connected IOTS; we let IOT S(I, O) denote the set of such IOTSs with input set I and output set O.
To characterize the common behavior of two IOTSs in IOT S(I, O) we use the intersection operation. The intersection S ∩ P of IOTSs S = (S, s 0 , I, O, h S ) and P = (P, p 0 , I, O, h P ) is an IOTS (Q, q 0 , I, O, h S∩P ) with the state set Q ⊆ S × P, the initial state q 0 = (s 0 , p 0 ), and the transition relation h S∩P , such that Q is the smallest state set obtained by using the rule ((s, p), x, (s , p )) ∈ h S∩P ⇐⇒ (s, x, s ) ∈ h S and (p, x, p ) ∈ h P . The intersection S ∩ P preserves only common traces of both machines; in other words, for each state (s, p) of S ∩ P we have Tr((s, p)) = Tr(s) ∩ Tr(p); moreover, out((s, p)) = out(s) ∩ out(p). Thus, Tr(S ∩ P) = Tr(S) ∩ Tr(P).
Given two IOTSs S and T, such that S has at least one sink state s ∈ S, the IOTS obtained by merging the initial state of T with a sink state s is called the chaining of S and T in the sink state s, denoted S@ s T.
For conformance testing, we consider a usual ioco relation.
Definition 1 Given two IOTSs P, S ∈ IOT S(I, O), S = (S, s 0 , I, O, h S ) and P = (P, p 0 , I, O, h P ), we write P ioco S if for each trace α ∈ Tr(S), we have that out(P-after-α) ⊆ out(S-after-α). If P ioco S then we say that state p 0 is a reduction of state s 0 . The reduction relation between states is also defined for states of the same IOTS S ∈ IOT S(I, O), namely, s 1 is a reduction of s 2 , if S/s 1 ioco S/s 2 .
We write P¨ïoco S, if not P ioco S. We notice that if the specification IOTS S contains some state that is a reduction of another state then there exist an implementation P ∈ IOT S(I, O) and state p ∈ P, that is a reduction of both states of S. Intuitively, the two states are "merged" into a single state in the implementation. As a result, a conforming implementation may have fewer states than its specification. This observation motivates the following definitions and statements.
Definition 2 Two states of S ∈ IOT S(I, O) are compatible, if there exists a state of an IOTS P ∈ IOT S(I, O) that is a reduction of both states; otherwise, i.e., if for any P ∈ IOT S(I, O), no state of P is a reduction of both states, they are distinguishable.
According to this definition, compatible states can be "merged" in an implementation IOTS into a single state and it can still be a reduction of the specification IOTS, however, any reduction of the specification IOTS cannot have a state that is a reduction of distinguishable states.
The compatibility of states can be easily determined by the intersection of IOTSs, a simple and inexpensive operation. By definition, if two states of a given IOTS are compatible, there exists a state of some input-complete, progressive IOTS which is a reduction of both states. Such a state is the initial state of the intersection of two instances of a given machine initialized in different states, since the intersection represents all the common traces of the two states. On the other hand, if the two states are distinguishable, the intersection is not a progressive IOTS. This fact is stated in the following lemma. Proof. Suppose that s 1 and s 2 are compatible. We show that S/s 1 ∩ S/s 2 ∈ IOT S(I, O), that is, S/s 1 ∩ S/s 2 is input-complete, progressive, deterministic and initially-connected. Let α ∈ Tr(S/s 1 ∩ S/s 2 ). Thus, α ∈ Tr(S/s 1 ) ∩ Tr(S/s 2 ). We have that s 1 = S/s 1 -after-α and s 2 = S/s 2 -after-α are also compatible. Hence, by Definition 1, there exists a state p of P ∈ IOT S(I, O), with P = (P, p 0 , I, O, h P ) that is a reduction of s 1 and s 2 . It holds that out(p) ⊆ out(s 1 ) and out(p) ⊆ out(s 2 ). As P is progressive, we have that init(p) = / 0, and thus there exists x ∈ out(p); hence, x ∈ init(s 2 ) ∩ init(s 2 ). It follows that (S/s 1 ∩ S/s 2 )-after-α is not a sink state, since it is followed by x, at least. Thus, S/s 1 ∩ S/s 2 has no sink state. If x is an input, then I ⊆ init(s 1 ) and I ⊆ init(s 2 ), since S is input-complete. Therefore, I ⊆ init((S/s 1 ∩ S/s 2 )-after-α), and S/s 1 ∩ S/s 2 is input-complete. As S is progressive, it does not have cycles with transitions labeled only with outputs. Hence, neither S/s 1 ∩ S/s 2 has such cycles, i.e., S/s 1 ∩ S/s 2 is also progressive. As S is deterministic and initially-connected, so are S/s 1 , S/s 2 and, consequently, S/s 1 ∩ S/s 2 . It follows then that S/s 1 ∩ S/s 2 ∈ IOT S(I, O).

Test definitions and problem statement
To simplify the discussion, we refer to inputs and outputs always taking the view of the implementation, IUT; thus, we say, for instance, that the tester sends an input to the IUT and receives outputs from it, and define test cases accordingly preserving the input and output sets of the specification IOTS S = (S, s 0 , I, O, h S ). Recall that δ is included into O; in particular, the output δ of a test case is interpreted as the fact that the tester executing the test case detects quiescence of the IUT.
Definition 3 A test case over input set I and output set O is an acyclic single-input output-complete  The problem of complete test suite generation for a given IOTS was addressed in [14,15]. To generate such a test suite a simple algorithm is suggested, which, however, should be executed an indeterminate number of times to achieve the test completeness w.r.t. the ioco relation. In the first work [14], only controllable test cases are generated; the problem with that solution is that the tester must be able to somehow preempt any output each time a test case prescribes sending some input to the IUT. In the second work [15], "the most important technical change with respect to [14] is the input enabledness of test cases, which was inspired by [11]". In terms of our definitions, test cases are uncontrollable; they contain quasi-stable states, where both inputs and outputs are enabled. The intention behind this is to address input/output conflict present in the specification IOTS, since the specification itself provides no clue how an implementation resolves input/output conflict. The behavior of the tester executing uncontrollable test cases may become nondeterministic (the tester has to execute one of the two mutually exclusive actions) and the test results may not always be reproducible. The approaches to generation of controllable tests that tolerate input/output conflicts based on the use of queues are elaborated in several work [4,6,7,11,12,17]. The problem is that one needs to know the size of queues to obtain a finite complete test suite.
In this paper, we demonstrate, first, that controllable tests that tolerate input/output conflicts can be constructed without knowing the size of queues, and second, that it is possible to obtain in a systematic way a finite set of controllable test cases which is a complete test suite in a finite set of IOTSs. The key assumption we make about the implementation IOTSs in the fault domain is that each implementation when it is a quasi-stable state with the input/output conflict, it does not produce any output if its input queue contains an input. We call such implementations input-eager. A subset of IOT S(I, O) that contains input-eager IOTSs is denoted IEIOT S(I, O). Finiteness of complete test suites results from further constraining this set by the number of its input states, as we demonstrate later.
Testing any input-eager IOTS allows one to use two controllable test cases dealing with input/output conflict; in a quasi-stable state one test case does not send any input and only observes output sequence concluded by quiescence and another one just sends input. In the latter case, the tester does not need to preempt IUT outputs, as an input-eager IOTS will not produce them since the input queue is not empty and contains the input from the tester.

Generating complete test suites for IOTS
In this section, we investigate whether a classical method for constructing a complete test suite for the FSM model can be reworked to achieve the same result for the IOTS model even with input/output conflicts, namely a test suite with controllable test cases complete in a finite fault domain, without transforming IOTS into Mealy machine. To demonstrate that it is in fact possible, we develop here a counter-part of the HSI-method [19] for the simplest case, when the FSM is completely specified, minimal, and the fault domain contains FSMs with the number of states not exceeding that of the specification machine.
The HSI-method for FSMs uses sets of distinguishing input sequences, so-called harmonized state identifiers, one per state, such that any two identifiers share an input sequence which distinguishes the two states. These input sequences are appended to state and transition covers in order to check that every state of the implementation corresponds to some state of the specification and every transition of the implementation corresponds to a transition of the specification.
Accordingly, we need first to define state and transition covers, as well as harmonized state identifiers for a given IOTS.

State and transition covers for IOTS
We first turn our attention to the notion of state cover, needed in tests to eventually establish a mapping from states of the specification to states of the IUT. We focus only on input states of the specification IOTS. First, to check the IUTs reaction to some input it is in fact sufficient to apply the input to a given input state, observe an output sequence, and if it is correct then check whether a proper input state is reached. Output state identification can thus be avoided. However, even considering only input states, some input state of the specification may not be mapped to any state of the IUT even if the latter is a reduction of the specification. Therefore, we should define a state cover targeting only those input states of the specification which have a corresponding state in any ioco-conforming implementation.
Definition 5 Given an initially connected IOTS S and an input state s, s is certainly reachable (creachable), if any P ∈ IOT S(I, O), such that P ioco S, contains an input state that is a reduction of s.
It turns out that the certainly reachable states can be determined by considering a submachine of S, similarly to the FSM case [10].
Lemma 3 An input state s of an IOTS S is c-reachable if S contains a single-input acyclic outputpreserving submachine of S which has s as the only sink state.
Proof. Let C s be a single-input acyclic output-preserving submachine of S, which has s as the sink state. The input state s is the only sink state in the submachine; hence all its completed traces converge in s. The submachine is output-preserving, this means that for each α ∈ Tr(C s ), if C s -after-α = s then out(C s -after-α) = out(S-after-α). Hence for any IOTS P ∈ IOT S(I, O), such that P ioco S, it also holds that out(P-after-α) ⊆ out(S-after-α), thus out(P-after-α) ⊆ out(C s -after-α). This implies that P should have at least one of the completed traces of C s ; let β be such a completed trace. It is easy to see that P ioco S implies that for any γ ∈ Tr(P), P-after-γ is a reduction of S-after-γ. Hence in any IOTS P ∈ IOT S(I, O), such that P ioco S, the state P-after-β is a reduction of S-after-β . The result follows, since β is a completed trace of C s and, thus, S-after-β = s.

Definition 6
Given a c-reachable input state s of an IOTS S, a single-input acyclic output-preserving submachine C s , which has s as the only sink state, is a preamble for state s.
Preambles for states can be determined by Algorithm 1, adapted from [10].
Algorithm 1 for constructing a preamble for a given input state. Input: An IOTS S and input state s ∈ S. Output: a preamble if the state s is c-reachable. Construct an IOTS R = (R, r 0 , I, O, h R ) as follows R := {s}; h R := / 0; While s 0 / ∈ R and there exist an input state s / ∈ R and nonempty A ⊆ I, such that for each x ∈ A, (s , x, s ) ∈ h S , and for each trace γ ∈ Tr(s ), where γ ∈ O * , there exists a prefix γ such that s -after-γ ∈ R.
End While; If s 0 / ∈ R then return the message "the state s is not c-reachable" and stop; Else let R = (R, r 0 , I, O, h R ), where r 0 := s 0 , be the obtained IOTS; Starting from the initial state, remove in each state all input transitions, but one, to obtain a singleinput submachine with the only sink state s; Delete states which are unreachable from the initial state; Return the obtained machine as a preamble for the state s and stop.
A preamble can be used to transfer from the initial state to c-reachable input states. For the initial state itself, the preamble is simply the trivial IOTS, which contains only the initial state. Figures 2.a, 2.b  and 3 show the preambles for states 2, 3 and 4, respectively, of the IOTS in Figure 1.
We assume that each input state of the specification IOTS S is c-reachable and the initial state is a stable state. An input state cover Z of S is a set of preambles, one for each input state, i.e., Z = {C s | s ∈ S in }.
In FSM-based testing, a state cover is extended to a transition cover, by adding all inputs to each transfer sequence of the state cover. In an IOTS, an input applied in an input state may be followed by a number of output sequences leading to various stable states, creating quiescent traces of IOTS. The set of all possible quiescent traces created by x ∈ I in input state s ∈ S in is {xγδ ∈ Tr(s) | γ ∈ O * }. We use Cov(s, x), called (s, x)-cover, to refer to an IOTS, such that Tr(Cov(s, x)) = {xγδ ∈ Tr(s) | γ ∈ O * } and the set of sink states is {s-after-xγ | γ ∈ O * }. For instance, Cov(2, a) for state 2 and input a of  the IOTS in Figure 1 has the trace a01δ , whereas Cov(1, a) has the traces a01δ , a111δ and a101δ . A transition cover V of S is the set of preambles of an input state cover chained with (s, x)-covers, i.e., V = {C s @ s Cov(s, x) | s ∈ S in , x ∈ I}. Notice that each bridge trace starting from a quasi-stable state s ∈ S in is covered by Cov(s , x), for some input state s and input x. More generally, we state the following lemma.
Lemma 4 Given an IOTS S ∈ IOT S(I, O) and a bridge trace β from an input state s ∈ S in , there exist input state s ∈ S in and input x, such that γβ γ δ ∈ Tr (Cov(s , x)), for some traces γ ∈ Tr(s ) and γ ∈ Tr(s -after-γβ ).
Proof. If β starts with an input, then the results follows directly, since with γ as the empty sequence β γ d is a quiescent trace starting at state s. If β starts with an output, then, β ∈ O * and s is a quasi-stable state. Notice that there exists γ ∈ O * , such that β γ δ ∈ Tr(s), since S is progressive. Moreover, there exist an input state s , a trace γ starting with x and followed by outputs, such that s -after-γ = s. Thus, γβ γ δ ∈ Tr (Cov(s , x)).
The IOTS, obtained by removing from R(s 1 , s 2 ) the sink state ⊥ s 2 and all transitions leading to it, is called a distinguisher of s 1 from s 2 and is denoted by W(s 1 , s 2 ).
Separator R(s 1 , s 2 ) can be obtained from the intersection S/s 1 ∩ S/s 2 = (Q, (s 1 , s 2 ), I, O, h S /s 1 ∩ S/s 2 ), similar to the case of FSM [10], as follows (Algorithm 2). First we determine the intersection S/s 1 ∩ S/s 2 and identify the states where the two IOTSs S/s 1 and S/s 2 disagree on outputs. For each such state, we add transitions leading to sink states ⊥ s 1 and ⊥ s 2 . In the final step, we determine a separator as a single-input output-preserving acyclic submachine of the obtained IOTS by removing inputs, as in Algorithm 1.
Algorithm 2 for constructing a separator for two input states. Input: An IOTS S and distinguishable input states s 1 , s 2 ∈ S in . Output: a separator R(s 1 , s 2 ). Construct the IOTS S/s 1 ∩ S/s 2 = (Q, (s 1 , Starting from the initial state, remove in each state all input transitions, but one, to obtain a singleinput submachine with the only sink states ⊥ s 1 and ⊥ s 2 ; Delete states which are unreachable from the initial state; Return the obtained machine as a separator for the states s 1 and s 2 , and stop. Notice that a separator of states s 1 and s 2 is obviously a separator of s 2 and s 1 , i.e., R(s 1 , s 2 ) = R(s 2 , s 1 ), whereas a distinguisher of s 1 from s 2 is different from a distinguisher of s 2 from s 1 , i.e., W(s 1 , s 2 ) = W(s 2 , s 1 ). Figure 4 shows a separator R(1, 4) obtained by Algorithm 2, as well as the corresponding distinguishers W(1, 4) and W(4, 1).
We consider only input-state-minimal specification IOTS, so we are interested in distinguishers of only input states. If s 1 is a stable state and s 2 is a quasi-stable state then the separator R(s 1 , s 2 ) is simple; it has a transition with δ leading from the state (s 1 , s 2 ) to state s 1 and a transition for each o ∈ out(s 2 ), leading to s 2 . Thus, a distinguisher of each stable state from any quasi-stable state has a single δtransition, we call it a quiescence distinguisher of a stable state s, denoted W δ (s). It should be included into a stable state identifier of the state s.
Definition 8 A state identifier of input state s, denoted ID(s), is a set of distinguishers W(s, s ) for each input state s distinguishable from s, including W δ (s) if state s is stable. A set of input state identifiers {ID(s) | s ∈ S in }, is harmonized, if for each pair of input states s 1 and s 2 , such that both are either stable or quasi-stable states, there exists a separator R(s 1 , s 2 ), such that W(s 1 , s 2 ) ∈ ID(s 1 ) and W(s 2 , s 1 ) ∈ ID(s 2 ).
For the IOTS in Figure 1, we have that ID(1) includes W δ (1) as well as W (1,4) in Figure 4.   Figure 5 shows the example of a test case, obtained by chaining the preamble C 2 , Cov(2, a) with the quiescent trace a01δ , and distinguisher W (1,4). Notice that the quiescence distinguisher W δ (4) of a stable state 4 is also used to identify this state, since the quiescent trace a01δ has it as a suffix. The f ail state is replicated to reduce the clutter.

Complete test suite
Completing each IOTS in the set D, we finally obtain a test suite T S = {TC(U) | U ∈ D}. Consider now the subset of IEIOT S(I, O) restricted by the number of input states less or equal to that of the specification IOTS S; we denote it by IEIOT S(I, O, k), where k is the number of input states in S. We state the main result of the paper. Before proving Theorem 1, we state some auxiliary results.
Lemma 5 Given two IOTSs P, S ∈ IOT S(I, O), if P is an initially connected submachine of S with the same initial state s 0 , then P ioco S.
Proof. Let α be a trace of S. We show that out(P-after-α) ⊆ out(S-after-α). Let s = S-after-a. If s / ∈ P, where P is the set of states of P, then out(P-after-α) = / 0, and the result follows. If s ∈ P, we have that out P (s) ⊆ out S (s). As s = P-after-α, the result also follows. Thus, P ioco S. Definition 9 Given two IOTSs P, S ∈ IOT S(I, O), P = (P, p 0 , I, O, h P ) and S = (S, s 0 , I, O, h S ), P is inputstate homeomorphic to S, if there exists a bijective map ϕ from P in to S in such that for every state p ∈ P in , each bridge trace γ ∈ Tr(p), it holds that ϕ(p)-after-γ = ϕ(p-after-γ).
P and S are input-state isomorphic, if P is input-state homeomorphic to S and S is input-state homeomorphic to P.
Notice that for output-deterministic IOTSs, input-state isomorphic IOTSs are also input-state homeomorphic. An output-nondeterministic IOTS S that is input-state homeomorphic to P differs from P in state names, as well as in the set of bridge traces in some states, since it may have fewer bridge traces, while input-state isomorphic IOTSs differ just in state names.
Corollary 2 Given two IOTSs P, S ∈ IOT S(I, O), if P is input-state homeomorphic to S, then P is inputstate isomorphic to an initially connected submachine of S with k input states and the same initial state. Proof. Let N ∈ IEIOT S(I, O, k), such that N passes T S. T S contains test cases where preambles of an input state cover are chained with harmonized identifiers to the respective states. Thus, for input states s and s , T S contains the test cases TC(C s @ s W(s, s )) and TC(C s @ s W(s , s)). Let α be a completed trace of C s and α be a completed trace of C s , such that α, α ∈ Tr(N). As N passes T S, no f ail state is reached when the distinguishers W(s, s ) and W(s , s) are applied after α and α , respectively. Since no state can reach sink state in both distinguishers (see Definition 7), we have that the states N-after-α and N-after-α are different, i.e., N-after-α = N-after-α . These are input states, thus, for each pair of input states of S there exist a pair of distinct states in N; consequently, N has at least k input states. As N ∈ IEIOT S(I, O, k), N has exactly k input states.
Let T ∈ (Z ∪ V ), t ∈ sink(T), α ∈ Tr(T) ∩ Tr(N), such that T-after-α = t, N-after-α ∈ N in . Similarly, let T ∈ (Z ∪ V ), t ∈ sink(T ), α ∈ Tr(T ) ∩ Tr(N), such that T -after-α = t . Notice that α and α are completed traces of IOTSs in the state or transition cover, which are also traces of N. We prove that S-after-α = S-after-α if and only if N-after-α = N-after-α. Let s = S-after-α and s = S-after-α . Suppose first that S-after-α = S-after-α. Thus, TS contains TC(T@ s W(s, s )) and TC(C s @ s W(s , s)), and as N passes T S, no f ail state is reached when the distinguishers W(s, s ) and W(s , s) are applied after α and α , respectively. Since no state can reach sink state in both distinguishers, we have that N-after-α = N-after-α . Suppose now that S-after-α = S-after-α. We prove by contradiction that N-after-α = N-after-α. Assume that N-after-α = N-after-α. Thus, let s be an input state, different from s = S-after-α. Let β ∈ Tr(C s ), such that β ∈ Tr(N). As T S contains TC(T@ s W(s, s )) and TC(C s @ s W(s , s)) and N passes T S, we have that N-after-α = N-after-β . Analogously, we can show that we have that N-after-α = N-after-β . Thus, N-after-α is distinct from k − 1 distinct input states of N and N-after-α is also distinct from k − 1 distinct input states of N. As N-after-α = N-after-α, N has k + 1 states, which contradicts the fact that N ∈ IEIOT S(I, O, k) and has at most k input states. Therefore, N-after-α = N-after-α. Thus, let ϕ be a bijection from the input states N in of N to the input states S in of S, such that for each completed trace χ of an IOTS in the state cover Z or transition cover V , which is also a trace of N, we have that ϕ(N-after-χ) = S-after-χ. Let p be an input state of N. There exists a completed trace α of an IOTS in the input state cover Z, such that α is also a trace of N and N-after-α = p. Thus, it holds that ϕ(N-after-α) = ϕ(p) = S-after-α. Let γ ∈ Tr(p) be a bridge trace, such that αγ is a completed trace of an IOTS in the transition cover V . Thus, it follows that ϕ(p)-after-γ = ϕ(N-after-α)-after-γ = (S-after-α)-after-γ = S-after-αγ = ϕ(N-after-αγ) = ϕ((N-after-α)-after-γ) = ϕ(p-after-γ), i.e., ϕ(p)-after-γ = ϕ(p-after-γ). Therefore, we have that N is input-state homeomorphic to S.
We can now prove Theorem 1.
Proof of Theorem 1. We first prove that T S is sound for S in IEIOT S(I, O, k). Let N ∈ IEIOT S(I, O, k), such that N ioco S. We have that for each test U ∈ T S, Tr pass (U) ⊆ Tr(S). Thus, Tr pass (U ∩ S) = Tr pass (U) ∩ Tr(S) = Tr pass (U). Since N ioco S, we have, for each α ∈ Tr(S), out(N-after-α) ⊆ out(S-after-α). Let β ∈ Tr pass (U ∩ N); hence, β ∈ Tr pass (U) and β ∈ Tr(N). As Tr pass (U) ⊆ Tr(S), we have that β ∈ Tr(S). It follows that Tr pass (U ∩ N) = Tr pass (U) ∩ Tr(N) ⊆ Tr pass (U) ∩ Tr(S) = Tr pass (U ∩ S) = Tr pass (U). Hence, Tr pass (U ∩ N) ⊆ Tr pass (U). As a result, N passes each test of T S, and T S is thus sound for S in IEIOT S(I, O, k) for the ioco relation.
We now prove by contradiction that T S is exhaustive for S in IEIOT S(I, O, k). Assume that T S is not exhaustive S in IEIOT S(I, O, k); thus, there exists N ∈ IEIOT S(I, O, k), such that N¨ïoco S and N passes T S. As N passes T S, by Lemma 6, we have that N is input-state homeomorphic to S; thus, by Corollary 2, N is input-state isomorphic to an initially connected submachine of S with k input states; hence, by Lemma 5, N ioco S, a contradiction. We conclude then that T S is exhaustive for S in IEIOT S(I, O, k).
Therefore, T S is complete for S in IEIOT S(I, O, k) w.r.t. the ioco relation.

Concluding Remarks
In this paper, we have investigated whether it is possible to construct a finite test suite for a given IOTS specification which is complete in a predefined fault domain for the classical ioco relation even in the presence of input/output conflicts. Our conclusion is that it is in fact possible; however, under a number of assumptions about the implementations and the specifications. We have proposed a generation method which produces a finite test suite, which is complete for a given fault domain. The issue of conflicts between inputs and outputs is tackled by assuming that the implementation is "eager" to read inputs and thus such conflict is solved in favor of input, i.e., outputs are produced only if no input is presented to the implementation. The proposed generation method is based on a classical FSM method. Thus, we rephrased the notions related to FSM generation methods, such as state cover, transition cover, state identifier, to the IOTS model. The method applies to IOTS that is minimal in the sense defined in the paper and each input state is reachable in any ioco-conforming implementation. A remarkable feature of the method is that it requires no assumption about distinguishability of output states or about their number in the specification and any implementation. Also no bound on the buffer's length in the implementation is required to generate a complete test suite.
Our future work will focus on extending the class of IOTSs for which the approach is applicable by relaxing the mentioned constraints.


extfieldsofstudy:
Computer Science
Medicine

text:
Cytochrome P450 site of metabolism prediction from 2D topological fingerprints using GPU accelerated probabilistic classifiers

Background The prediction of sites and products of metabolism in xenobiotic compounds is key to the development of new chemical entities, where screening potential metabolites for toxicity or unwanted side-effects is of crucial importance. In this work 2D topological fingerprints are used to encode atomic sites and three probabilistic machine learning methods are applied: Parzen-Rosenblatt Window (PRW), Naive Bayesian (NB) and a novel approach called RASCAL (Random Attribute Subsampling Classification ALgorithm). These are implemented by randomly subsampling descriptor space to alleviate the problem often suffered by data mining methods of having to exactly match fingerprints, and in the case of PRW by measuring a distance between feature vectors rather than exact matching. The classifiers have been implemented in CUDA/C++ to exploit the parallel architecture of graphical processing units (GPUs) and is freely available in a public repository. Results It is shown that for PRW a SoM (Site of Metabolism) is identified in the top two predictions for 85%, 91% and 88% of the CYP 3A4, 2D6 and 2C9 data sets respectively, with RASCAL giving similar performance of 83%, 91% and 88%, respectively. These results put PRW and RASCAL performance ahead of NB which gave a much lower classification performance of 51%, 73% and 74%, respectively. Conclusions 2D topological fingerprints calculated to a bond depth of 4-6 contain sufficient information to allow the identification of SoMs using classifiers based on relatively small data sets. Thus, the machine learning methods outlined in this paper are conceptually simpler and more efficient than other methods tested and the use of simple topological descriptors derived from 2D structure give results competitive with other approaches using more expensive quantum chemical descriptors. The descriptor space subsampling approach and ensemble methodology allow the methods to be applied to molecules more distant from the training data where data mining would be more likely to fail due to the lack of common fingerprints. The RASCAL algorithm is shown to give equivalent classification performance to PRW but at lower computational expense allowing it to be applied more efficiently in the ensemble scheme.

Background
The prediction of sites and products of metabolism for xenobiotic and endogenous compounds is an important avenue of research, playing an influential role in the development and use of pharmaceuticals, cosmetics, nutritional supplements and agrochemicals. Toxicity of metabolites can play a major role in the withdrawal http://www.jcheminf.com/content/6/1 /29 giving rise to C=C epoxidation, aromatic C oxidation, S oxidation and C-H hydroxylation reactions, the last example often leading to N-dealkylation or O-dealkylation if oxidation occurs on a suitable leaving group in an amine or ether moiety.
A host of computational approaches to predict SoMs have been developed as an alternative or aid to the resource and time consuming nature of experimental investigation. These approaches can be either ligandbased, where the structures and properties of known substrates or non-substrates are modelled to develop structure-activity relationships, or structure-based, where the structure of the metabolising CYP enzyme and its interactions with ligands are modelled. The reader is referred to the many comprehensive review papers [3][4][5][6][7] for an overview of the current computational tools to predict SoMs.
Many methods consider reactivity and accessibility factors since a SoM must be sufficiently reactive and also able to come into close proximity to the reactive heme centre. One such example is SMARTCyp [8], a Java-based SoM predictor that uses a database of activation energies for various pre-defined ligand fragments to assign reactivity estimates to matching moieties in a query ligand, with an accessibility descriptor used to tune the ranking.
Other methods take the accessibility consideration further and employ docking techniques to refine the predictions from reactivity approaches. Examples of these methods include IMPACTS [9], which combines docking with a fragment based reactivity approach, and a recently published approach [10] that makes use of a tethered docking methodology using GOLD [11] combined with a reactivity approach based on hydrogen bond order descriptors and a novel implementation of the average local ionisation energy.
In contrast to these approaches the methods described in this work do not require the explicit modelling of ligand binding or reactivity, but make use of machine learning techniques applied to an appropriate, representative data set. Various machine learning methods have been applied to the problem of SoM metabolism with some of the major contributions summarised below.
An example of a data-mining approach is MetaPrint2D [12], an online metabolism prediction tool trained on the Accelrys Metabolite Database [13] that makes SoM predictions based on occurrence counts of atomic fingerprints within the database where they appear as SoM versus non-SoM. If matching sites are not found in the database, Metaprint2D informs the user and makes no predictions rather than extrapolating beyond its domain of applicability.
Many methods employing machine learning techniques generate a wide-range of descriptors for each atomic site in the data set often including quantum chemical and electronic descriptors. An example is RegioSelectivity (RS)-predictor [14,15] which uses a Support Vector Machine (SVM) to predict SoM using 148 topological and 392 quantum chemical atomic descriptors where some of these descriptors are modified to include contributions from neighbouring atoms. A neural network approach called Xenosite [16] has also been applied to this descriptor set but combined with other molecular descriptors and fingerprint descriptors based on the Daylight [17] definition. A probability score that each atomic site is a SoM is obtained allowing the different sites in the molecule to be ranked with improved predictive performance over (RS)-predictor reported.
Another study [18] combines descriptors based on the electronic structure of the molecule with explicitly calculated activation energies [19,20], and also incorporates Solvent Accessible Surface Area (SASA) descriptors calculated using MOE [21]. Classification of the atomic sites in the data set into SoMs and non-SoMs was performed using random forest/ensemble decision trees, with the activation energy shown to be the most important in determining SoM.
A further method [22] with relevance to small endogenous molecules makes use of the Kyoto Encyclopedia of Genes and Genomes (KEGG) pathway database [23] where 4843 reactions were classified into 80 classes. SMARTS patterns were used to define chemical substructures (reaction centres and surrounding regions) with various descriptors used to encode these sites including electronic, energetic, topological, distance and steric. For each reaction centre a SVM binary classification model was trained and the score obtained for each potential SoM in a query molecule was used to rank the candidate reaction centres.
The computational expense of using quantum chemical descriptors is addressed by FAME [24], a metabolism prediction tool that applies random forest models to the Metabolite [13] database. It calculates atomic descriptors using the CDK [25] relating to charge and molecular topology and generates SoM predictions in a few seconds per molecule. FAME has other benefits since it is not just a predictor of CYP metabolism but reflects the broader enzyme reactions documented in the Metabolite database and can be filtered for Phase-I and Phase-II metabolism in human, rat and dog.
A recent publication [26] describes an approach to SoM prediction that applies the PASS algorithm to atom environment fingerprints encoded with 2D descriptors. This allows the method to be faster than those methods that must first generate 3D structures to calculate quantum chemical descriptors and gives results that are competitive with RS-Predictor and SMARTCyp.
This paper takes a similar approach using the 2D topological circular fingerprint [27,28] of atomic sites within a http://www.jcheminf.com/content/6/1/29 molecule as the sole descriptor making the method computationally less expensive than those that use 3D descriptors. Three probabilistic classifiers have been applied to the problem of xenobiotic SoM prediction: the Naive Bayesian (NB), the Parzen-Rosenblatt Window (PRW) and a novel method called RASCAL (Random Attribute Subsampling Classification Algorithm) that will be presented in the Methods section. In all classifiers the machine learning technique was applied on an ensemble basis by randomly subsampling descriptor space and treating each sub-classifier as one vote in an overall classification.
The kernelised nature of the PRW and RASCAL algorithms allied with the ensemble approach lends itself to a parallel implementation exploiting the massively parallel processing capability of Graphical Processing Units (GPUs). The computing industry is moving towards a parallel model as the limitations and capabilities of modern semiconductor manufacturing mean that ever increasing performance from a single processor is no longer possible [29]. In recent years, GPUs have become increasingly competitive with regard to programmability, speed and price, with the release of CUDA (Compute Unified Device Architecture) providing a standard C-like interface allowing scientists to exploit the parallel power of the GPU. The CUDA model operates by launching blocks of threads that are executed on stream multiprocessors (SMs) concurrently. Threads and blocks can be referred to by identification numbers allowing each to operate on a different portion of the data, where threads in a common block can communicate via a localised shared memory.
Recent developments in GPU accelerated classification tools include implementations for support vector machines [30][31][32], neural networks [33], k-nearest neighbours [34] and a parallel tool for the classification of remotely sensed imagery [35]. The techniques described in these studies could lead to similar efficiency gains when applied to cheminformatics classification problems and in the remainder of this paper GPU accelerated probabilistic classifiers are applied to the problem of SoM identification. The CUDA implementation released as part of this work could be applied to other binary or multi-class data sets, where in the case of RASCAL and NB the feature vectors would need to consist of integer or binary values. It is hoped that this implementation would be of interest to members of the cheminformatics community applying classification approaches to large data sets where performance is hindered by high computational demands.
In the Methods section the data sets and descriptors are presented, along with the three probabilistic classifiers (PRW, RASCAL and NB) and a discussion of the CUDA implementation. In the Results section the classification performance of the different methods is presented in terms of the Matthews Correlation Coefficient (MCC), area under the ROC curve and the percentage of the data sets where a SoM is identified in the top k positions. The effect of varying the size of the circular fingerprints used to describe atomic sites is investigated and a benchmarking analysis comparing the speed performance of the CUDA implementation on a Tesla C2075 GPU and a GeForce GT640 GPU to reference is presented. The important inferences from this work are presented in the Conclusions section.
To emphasize the benefits and novel aspects of this work it is important to point out that the SoM prediction models are built from 2D topological circular fingerprints without the requirement for complex quantum chemical and 3D descriptors. RASCAL combines the classification performance of the PRW with greater computational speed and hence could be applied to other much larger data sets. The data sets employed here are relatively small and show that SoMs can be identified within data sets of the order of 100's of molecules being of potential interest to pharmaceutical companies with limited data on a specific series of molecules.

Data sets
The machine learning approaches used in this study have been applied to the publicly available CYP 3A4, 2D6 and 2C9 data sets that originate from those initially released in the supporting information of the RS-Predictor paper [15] but further curated [9] with reference to the primary literature to identify and eliminate conflicting information. Open Babel v2.3.1 [36] was used to generate the protonation state of each ligand at pH 7.4 and the mol2 files generated are made available in the Additional files. The data sets have been sampled on a leave-one-out-crossvalidation basis to generate results that are comparable with other reported methods [16].
The feature vectors used to describe the atomic sites in each molecule are 2D topological circular fingerprints [27,28] based on the occurrence counts of SYBYL [37] atom types at different topological distances from the atom in question (see Figure 1 for a pictorial representation of the construction of these fingerprints). The size of the circular fingerprints can be varied by choosing different bond depths and for this study separate training sets were created for bond depths ranging from 0-8, thus allowing the impact of bond depth on classification performance to be assessed. A Java program was written to read in the data sets in mol2 [13] format and generate the circular fingerprints creating two classes: those circular fingerprints associated with a SoM and those not associated with a SoM. The circular fingerprints assigned to these two classes for each data set and bond depth were used as the inputs to the machine learning approaches described in this work. The data sets for each isoform for http://www.jcheminf.com/content/6/1/29 Figure 1 Topological circular fingerprints. Graphic to represent the construction of a circular fingerprint to a bond depth, d, of 6 using counts of SYBYL atom types at each level.
bond depths ranging from 4-6 are made available in the Additional files section in Additional files 1, 2, 3, 4, 5, 6, 7, 8 and 9. The mol2 files used to generate these circular fingerprints are also made available in the Additional files section in Additional files 10, 11 and 12.

SoM prediction
The SoM classification performance of each approach described in the Methods section was assessed for each isoform data set using feature vectors calculated at each of the bond depths ranging from 0-8. These methods have been implemented on an ensemble subsampling methodology, hence as described previously the length of the subsample, q, needs to be optimised. Therefore, for each classification model q was varied from an initial value of 5 to the full number of features L in increments of 5, with the Matthews Correlation Coefficient (MCC) [38] and the area under ROC curves used to compare classification performance. Selection of the j parameter is a balance between sufficiently sampling feature space versus computational load, with a value of 201 found to be suitable in this case. The graphs shown in Figure 2 show classification performance against j for models with q = 40 and bond depth ranging from 4-6 and show that by j = 201 the classification performance has largely reached a plateau.
In this way the probability that an atomic site is a SoM can be calculated allowing all sites in a molecule to be ranked. The percentage of the data set where a SoM is Figure 2 Impact of number of subsamples, j. Graphs showing classification performance for the three data sets in terms of MCC against number of subsamples j for models built using circular fingerprint bond depths ranging from 4-6. A value of j = 201 was chosen to run the classification models. http://www.jcheminf.com/content/6/1/29 identified in the top two (top-2%) and top three (top-3%) predictions was calculated to allow comparisons to other SoM identification methods. When calculating the top-2% and top-3% values steps were taken to identify atoms in equivalent sites to ensure that such sites are only included once in predictions. This was achieved by generating full circular fingerprints for each atomic site in the same way as described previously but this time spanning the entire ligand, with equivalent atomic sites defined as those with identical circular fingerprints.

CUDA implementation
The three probabilistic classifiers have been implemented using the Nvidia Nsight [39] integrated development environment for CUDA/C++ released as part of CUDA Tools 5.5. A benchmarking analysis has been carried out comparing the performance speed of an Nvidia C2075 Tesla GPU and an Nvidia GT640 GeForce GPU against a reference CPU implementation running on a single Intel Xeon E5506 at 2.13GHz.
The source code is available in a public repository (https://bitbucket.org/jdt42/probclassifier_cuda) and could be applied to other classification problems where the input files are formatted in the appropriate manner for this tool. The code exploits the parallel nature of GPU's by aligning the dimensions of the classification problem, such as number of feature vectors N and number of subclassifiers j, with the parallel architecture of CUDA where computational work is kernelised and spread over blocks of threads. The code makes use of atomic operations and so requires a CUDA enabled GPU with a compute rating of ≥ 1.1.

Probabilistic classifiers
Cheminformatics classification approaches that compare structural similarity to known molecules tend to be more successful if they allow for some degree of uncertainty (fuzziness) [40]. This means one treats the attributes representing the data items under study, and the class they are associated with as stochastic variables. In this scenario the classification problem can be viewed as a hypothesis testing task; this requires estimates of the probability densities of the attributes for each class. Estimates of these probability densities, coupled with an appropriate decision rule, constitute what is commonly referred to as statistical (or probabilistic) classifiers [40,41].
In the probabilistic pattern recognition framework, it is assumed that there is an unknown probability distribution p that underlies any relationship in the available data, D, where the data points belonging to D are drawn from a product space X × Y where X represents input patterns/objects and Y represents the class space. In this setting, the purpose of a learning algorithm is to discover the probability distribution p that captures the "functional" relationships that may exist between X and Y . In a typical pattern classification scenario the available data set D is finite and is defined as , where x i ∈ X; y i ∈ Y and N refers to the size of the given sample data.
The process of finding an appropriate probabilistic classification model p(x i , y i ) involves relating x i probabilistically to its associated y i , where p(x i , y i ) refers to the probability of (x i , y i ) occurring.
In practice, we are often interested in the posterior probability that a given pattern x i is associated with y i . The essence of our task is to generate an algorithm that is capable of inferring probabilistic classification rules from the given training set with the ability to generalise to new patterns. The input pattern x i is an L-dimensional mathematical vector that inhabits an abstract L-dimensional space. The pattern vector x i consists of L elements x i = (x i1 , x i2 , . . . , x iL ) that represent the information we have about L different but relevant properties of the i th pattern. The class label y i often denotes a set of predefined classes In this work we are concerned with classification problems where the elements x il can assume integer values being the counts of SYBYL atom types at specific bond depths from the atom described by x i . For the sake of clarity the index i in both x i and y i will be dropped in the rest of the paper; unless otherwise stated.
Bayes' theorem allows us to compute p(x, ω α ) (i.e., p(x, y)) from a priori and conditional probabilities. This means that the class posterior probability p(ω α |x) of a given pattern x being associated with ω α [41] can expressed in the form [41][42][43][44]: where p(ω α ) is the a priori probability of class ω α and can be estimated from the class proportions in the training data set; p(x|ω α ) is the class conditional probability of x belonging to class ω α ; and p(x) is given by: To make a probabilistic classification on a new pattern x, the probability of x belonging to each class ω α needs to be computed, with x assigned to the class with the highest probability value:

P(ω α |x)
The prediction efficiency of the generated classifier can be validated by comparing classification predictions made by the model with actual known classes. Once the model is deemed reliable, it can then be used to make predictions http://www.jcheminf.com/content/6/1/29 about the behaviour of real world patterns coming from the same domain, X, as the given training set.
Clearly the estimation of the probability function p(x|ω α ) is the most important step in the estimation of p(ω α |x), vide supra. Thus, over the years a number of approaches to obtain estimates of p(x|ω α ) have been developed [44][45][46].
When the data are sparse in the descriptor/input space, it can become difficult to generate a good estimate of p(x|ω α ). This may result in a probabilistic classifier (a single classifier) with poor generalisation performance. This problem is also encountered when one tries to construct non-probabilistic classifiers on a data set sparse in the descriptor space.
There are different approaches that can be used to improve the generalisation performance of single classifiers. Feature selection schemes [41]; regularisation methods [42,46]; and the so-called ensemble learning technique (which is currently popular [42,47,48]) are good examples of these approaches. In the ensemble technique, the scheme employed in this work, the classification of a new pattern x is typically made through majority voting of the classification predictions of j(> 1) single (or base) classifiers. Empirical and theoretical results indicate that an ensemble of base classifiers gives improvements in generalisation over the individual classifiers [49], providing the base classifiers are not correlated with one another. It was suggested that an effective method of achieving uncorrelated individual classifiers in an ensemble is by training the single classifiers using randomly selected q distinct attributes/features of the available L features where q ≤ L [49] and the q-dimensional descriptor vector is denoted by x q .
It is important to note that, in this ensemble approach, the number of training data points remains the same, i.e., N. Thus, the relative (with respect to q, the descriptor subspace dimension) training sample size increases [50], which in turn can improve the approximation of the class-conditioned probability from the training set.
Three probabilistic classifiers based on the ideas briefly described in the preceding paragraphs have been used to create SoM prediction tools, namely the Naive Bayesian (NB) [41,42], Parzen-Rosenblatt Window (PRW) [51] and an internally developed methodology called RASCAL. The latter two approaches are kernel based, vide infra.
In the following sections we describe how p(ω α |x q ) is estimated in each of the classification methods. The atomic site and its class (SoM or nonSoM) are represented by x q , and ω α , respectively. Note that in this work M = 2, i.e. we are only dealing with 2 classes ω 0 and ω 1 , where ω 0 refers to SoM and ω 1 denotes nonSoM. Finally it is assumed that all a priori class distributions are equal, i.e., p(ω 0 ) = p(ω 1 ).

Naive Bayesian (NB)
In the Naive Bayesian case, the class conditional p(x q |ω α ) can be estimated as where with C l being the number of times descriptor x q l assumes the same value in class ω α and N α is the number of training items belonging to class ω α .
Since p(ω 0 ) = p(ω 1 ), the posterior probability prediction for membership of a particular class is computed as The data item x q is predicted to be in the class with the highest posterior probability p(ω α |x q ), and in the case where equal posterior probabilities are calculated for two classes they are ranked arbitrarily. The final class membership probabilities are calculated as the ratio of the number of votes for that class divided by the total number of subclassifiers j.

Kernel based probabilistic classifiers
In kernel based methods, the average similarity, S i α , of a test atom x where N α represents the number of training data items belonging to class ω α and the kernel function K x Two different kernel functions have been implemented: the PRW and a Dirac kernel [52] used in the implementation of RASCAL, both described in the next subsections. http://www.jcheminf.com/content/6/1/29

Randomised attribute subsampling classification algorithm (RASCAL)
In this study we present a probabilistic classifier called RASCAL that uses a Dirac kernel function as shown below.
In the case where the descriptors are defined over the binary domain it has been shown that this kernel is equivalent to a full expansion in Radmacher Walsh polynomials [53]. However, in this application the circular fingerprints used to describe the atomic sites are integer valued although the closed form of the kernel shown above can be applied to all discrete valued feature vectors.

Parzen-Rosenblatt window (PRW)
In this study, a Gaussian kernel has been used for PRW defined as is a measure of the distance between x q i and x q k , q is the number of features and h is a smoothing parameter, where a value of h = 0.1 was found to give good performance. Figure 3 summarises the classification results for four molecules chosen at random from the CYP 3A4 data set using the scenario with a bond depth of 4, q = 45, j = 201 and the RASCAL classifier. SoMs have been labelled with a green circle and the scores for the top three predictions are labelled against the atom: green text is used where a SoM is identified, red text is used with a corresponding red ring where a non-SoM is identified. A SoM is identified in the top 3 predictions for all molecules, and the top 2 predictions for all except Lovastatin, reflecting the strong classification performance observed across the entire data set.

Circular fingerprint depth analysis
The graphs in Figure 4 show classification performance for the three data sets against the bond depth used to generate topological circular fingerprints, with the first row of graphs showing the Matthews Correlation Coefficient (MCC) and the second row of graphs showing the top-2%. Classification performance on an MCC basis is shown in Table 1  of each atomic site is being used, although the rate of improvement tends to slow with bond depth showing that the more local descriptors are most important. Classification performance on a top-2% basis shows similar trends although a plateau in classification performance tends to be reached earlier at a bond depth of 4-5.  Table 2 shows the classification performance for circular fingerprint bond depths of 4-6 and it can be seen that they encode sufficient information for PRW and RASCAL top-2% performance of over 82% for all 3 isoforms, results that are competitive with other published methods [14,15], see Table 3.

Analysis of subsample length on classification for bond depths of 4-6
As described previously classification performance is dependent on the subsample length q and the number of subclassifiers j. The graphs in Figure 5 show the classification performance in terms of MCC against q for each of the models based on circular fingerprint bond depths ranging from 4-6. It can be seen that PRW and NB are less sensitive to q than RASCAL, which is to be expected since RASCAL is in effect a subsample matching algorithm and if the subsample becomes too long then no matching instances will be found in the training set for either class. Therefore when classifying a data set using RASCAL it is necessary to parametrise carefully to find a suitable value for q. For PRW and NB classification performance tends to plateau at high q when applied to these data sets and using a PRW smoothing parameter of h = 0.1. For these approaches the extra computational cost of an ensemble approach is not justified in terms of improved performance and a standard implementation running over all L descriptors would be more suitable. It can be seen that PRW and RASCAL give similar classification performance once the parameter q has been optimised, with both systematically outperforming the NB. This is reinforced by the ROC curves shown in Figure 6 where PRW and RASCAL performance tracks above that for NB.

Significance of molecular similarity
Machine learning becomes more challenging when test data is more dissimilar to training data. To investigate the ability of these methods to be applied to molecules more dissimilar from the training data a test set (TS1) representing 20% of each isoform data set was selected at random with the remaining 80% forming the training set. A second test set (TS2) was then defined as a 50% subset of TS1 representing the molecules most dissimilar to the training set, with Open Babel [36] used to measure molecular similarity using the default fingerprint. The SoM prediction performance is shown in Table 4 and shows that a worsening in performance in TS2 is more pronounced in the CYP 3A4 data set for the RASCAL classifier and on a top-2% basis in the CYP 2D6 data set for the PRW classifier indicating that care must be taken when extrapolating into chemical space more dissimilar to the training data although reasonable predictive performance is maintained.

Benchmarking analysis
A comparison of the running times of the PRW, RASCAL and NB algorithms on the three different platforms is given in Table 5 and the benefits from running in parallel are apparent. The results discussed previously have shown that RASCAL gives classification performance equivalent to PRW and so to become relevant and competitive as a classifier it is necessary to demonstrate that RASCAL is a faster more efficient algorithm. The relevant factors regarding the computational expense of the RASCAL and PRW algorithms are discussed next. The reminder of this section makes use of the following variables to describe the computational expense of the various algorithms: N refers to the size of the training set for a particular class; j refers to the number of subsamples; q refers to the subsample size; and L refers to the full length of the feature vector. Using these definitions the PRW algorithm computational expense when subsampling descriptor space, PRW sub , can be estimated as whereas the computational expense of RASCAL can be estimated as It should be noted that the RASCAL estimate is an upper bound. Only in the case where the training and test subsamples are identical are all q features compared otherwise the feature by feature comparison is halted as soon a difference is noted. Therefore the 15-fold faster running time of RASCAL over PRW can be justified by the lower computational expense, the early termination of the RAS-CAL kernel where relevant and the simpler nature of the RASCAL kernel compared to the PRW kernel.
However, as demonstrated in the Results section there is no benefit to performing subsampling with PRW, hence a more valid evaluation of algorithm running times is by comparison against PRW running over all L features http://www.jcheminf.com/content/6/1/29 Figure 5 Impact of subsample length, q. Graphs showing classification performance for the three data sets in terms of MCC against subsample length q for models built using circular fingerprint bond depths ranging from 4-6. The number of iterations j = 201. RASCAL requires careful parametrisation of q due to its sensitivity to this parameter.
without subsampling, PRW all , where the computational expense can be estimated as Therefore RASCAL is more likely to run faster than PRW when q L. In the data set with bond depth of 6, where L = 175, applying RASCAL with q = 40 and j = 201 gives a speed increase of 1.5 − 2.0 compared to PRW running over all features. However, the case for using RASCAL is likely to become much more compelling when using data sets consisting of longer feature vectors where it is more likely that RASCAL models can be used where q L. NB runs faster than RASCAL since it is possible to precompute the counts of common features between test data items and each training class so that the training data items only need to be parsed once, albeit at the price of poorer classification performance. http://www.jcheminf.com/content/6/1/29 Figure 6 ROC curves. Graphs showing ROC curves for the three data sets using the best classification models built using circular fingerprint bond depths ranging from 4-6.

Conclusions
The probabilistic classifiers outlined in this paper based on 2D topological fingerprints give SoM predictive performance that is competitive with other machine learning methods that employ complex 3D descriptors, enabling conceptually simple and efficient classification models to be built. Data mining approaches often suffer when fingerprints from a test molecule are not contained in the training data, but descriptor space subsampling and the use of classifiers that measure a distance between vectors instead of exact matching help to alleviate this problem.
This enables the creation of classification models that can be based on relatively small data sets but still applicable to molecules more distant from the training data where data mining would be more likely to fail due to the lack of common fingerprints. Hence the methods could be of interest to pharmaceutical companies studying a series of molecules with only of the order of 100's of data points available.
RASCAL and PRW were found to give similar predictive performance with PRW identifying a SoM in the top 2 predictions for 85%, 91% and 88% for the CYP 3A4, 2D6 http://www.jcheminf.com/content/6/1/29  and 2C9 data sets respectively, whereas for RASCAL the figures are 83%, 91% and 88%, respectively. This performance is competitive with other published machine learning methods [14,15] but is achieved using 2D descriptors. This suggests that there are common patterns in the local structure of SoMs in the data sets that are captured by the atomic circular fingerprints and can be identified by machine learning methods. RASCAL gives similar classification performance to PRW but at lower computational expense making it suitable for use on large data sets and particularly for the ensemble schemes outlined in this paper. The speed boost from using RASCAL is likely to become more apparent for classification problems where q L (where q is the subsample length and L is the full length of the feature vector) and in these situations the benefits from using RASCAL are likely to become more compelling.
The suitability of using CUDA/C++ to exploit the parallel capabilities of GPU hardware for classification problems has been demonstrated and it is hoped that the source code will be of use to other researchers in the field. Further enhancements to the implementation could include maximising the use of faster memory (shared, texture and constant), implementing task parallelism using streams and implementing code to run on multiple GPUs, all of which should further improve the speed-up in performance compared to the reference.
In summary it has been shown that probabilistic classifiers implemented using randomly selected subclassifiers on an ensemble basis using 2D topological circular fingerprints as descriptors can give strong SoM predictive performance. However, as with all machine learning methods, the models are likely to be most relevant within their domain of applicability and are likely to perform less well against novel molecules that are very different from those in the training set.