# Application of Stochastic Automata Networks for Creation of Continuous Time Markov Chain Models of Voltage Gating of Gap Junction Channels

Authors: Mindaugas Snipas; Henrikas Pranevicius; Mindaugas Pranevicius; Osvaldas Pranevicius; Nerijus Paulauskas; Feliksas F. Bukauskas
Journal: BioMed Research International
 (2015)

---

## Abstract

The primary goal of this work was to study advantages of numerical methods used for the creation of continuous time Markov chain models (CTMC) of voltage gating of gap junction (GJ) channels composed of connexin protein. This task was accomplished by describing gating of GJs using the formalism of the stochastic automata networks (SANs), which allowed for very efficient building and storing of infinitesimal generator of the CTMC that allowed to produce matrices of the models containing a distinct block structure. All of that allowed us to develop efficient numerical methods for a steady-state solution of CTMC models. This allowed us to accelerate CPU time, which is necessary to solve CTMC models, ∼20 times.


---

## Body

## 1. Introduction

Gap-junctional communication plays an important role in many processes, such as impulse propagation in the heart, communication between neurons and glia, organ formation during early development, regulation of cell proliferation, and metabolic exchange between cells of various tissues, including the lens that lack blood circulation. Gap junction (GJ) channels are formed of connexin (Cx) proteins, which belong to a family of integral membrane proteins exhibiting a tissue specific expression pattern. GJs provide a direct pathway for electrical and metabolic signalling between the cells [1]. In humans, twenty-one isoforms of Cxs form GJ channels [2]. Each GJ channel is composed of two hemichannels (HCs), both oligomerized of six Cxs. Cxs have four alpha helical transmembrane domains (M1 to M4), intracellular N- and C-termini (NT and CT), two extracellular loops (E1 and E2), and a cytoplasmic loop (CL) [3]. Docking of two HCs from neighbouring cells leads to formation of the GJ channel composed of 12 Cxs.However, despite such complexity, all GJ channels share the same common property—sensitivity to transjunctional voltage (Vj), called voltage gating. Junctional conductance (gj) measured under steady-state conditions decays symmetrically in response to Vj of either polarity, which have been explained by the presence of a Vj-sensitive gate in each opposed HC [4]. Such property, being inherently quantitative, is amenable to the investigation by computational methods.Earlier, we developed stochastic 4- and 16-state models of voltage gating, containing 2 and 4 gates in series in each GJ channel. In order to demonstrate that the proposedVj-gating model is adequate, it is necessary to compare its output to experimental results. For example, the proposed stochastic 4- and 16-state models of Vj-gating contained a sizable number (>10) of parameters and for their estimation global optimization (GO) algorithms were successfully used [5, 6]. The simulation of Vj-gating was performed with different sets of parameters. However, for the estimation of a global minimum, it typically requires running thousands of iterations, each lasting for up to 10 seconds, and consequently GO takes tens of hours or days. Thus, the reduction of the computation time that is needed for GO of experimental data is a critical task.In previous work a discrete time Markov chain (DTMC) model was used [7]. This model described the GJ channel containing 12 gates. In such model, differently from the 4- and 16-state models, it was assumed that each Cx of the GJ channel contains the gate. Since all 12 gates operate at the same time, construction of the transition matrix is not a trivial task. Therefore, transition matrix P is dense and when direct methods, that is, Gaussian elimination, are applied, the run-time complexity of steady-state probabilities is in the neighbourhood of On3. Numerical experiments showed that the use of DTMC model, as opposed to simulation, reduced CPU time ~18- and ~7-fold for 4- and 16-state models, respectively.When using Markov chain models one needs to build the probability transition matrix and to estimate steady-state probabilities at differentVjs at ~1000 different time moments during a single iteration. Typically, GO of experimental data require to use 500–5000 iterations to find a global minimum. Altogether, this will require to perform ~2 500 000 simulations using Markov model. Thus, it is evident that modeling requires fast construction of the matrix of transition probabilities (transition rates) and fast solution of the steady-state probabilities because the amount of central processing unit (CPU) time is high even at relatively small number of states. In our prior studies [8], we already used continuous time Markov chain (CTMC) model of GJs gating. A transformation of the transition probabilities into transition rates is necessary to generate CTMC model with the same steady-state probabilities, but infinitesimal generator matrix of CTMC model is sparse. For example, infinitesimal generator of GJ model presented in [8] was a tridiagonal matrix. Therefore, generation of matrix and modeling of GJs under steady-states conditions using the CTMC model require smaller amount of CPU time compared to using the DTMC model.In the present study, we used CTMC for the modeling of GJs containing two voltage-sensitive gates, each of which is composed of six subgates attributed to each Cx; in stochastic 4- and 16-state gating models each gate is regarded as one unit. We also used a stochastic automata network (SAN) formalism for the Markov model specification. SAN formalism allowed accelerating generation of the transition-rate matrices.In previous study [8] we used piece linear aggregate (PLA) formalism for CTMC model creation. PLA formalism allows building and storing infinitesimal generator of Markov chain model automatically, but matrix structure cannot be easily deduced, especially in more complex models. On the other hand, SAN formalism is a method that is based on using tensor algebra matrix operations. Consequentially, infinitesimal generators have the distinct structure allowing for very efficient application of the numerical methods. Here, we present SAN description of CTMC models of three different GJ models and analyze the efficiency of numerical solution. Since CPU time depends on software and its implementation, we focused on more universal evaluation of a complexity of algorithms. It is based on the exact number of mathematical operations, which is necessary to perform steady-state probabilities calculation.Our studies showed that if a proper numerical method is applied, then a steady-state solution of the proposed CTMC model of GJs requires 10–20-fold less CPU time compared to DTMC models. We suggest that the use of iterative methods might be especially beneficial in estimation of gating parameters, since it requires repetitive simulations with different sets of parameters. We showed that using a previous solution for evaluating continuous one, whenVj changes are small (<1 mV), allows reducing the number of iterations for at least 30 percent.


## 2. Methods

### 2.1. Markov Chain Modeling

We assume the stationary analysis of a homogenous irreducible Markov chain with a finite number of system states, denoted byn. Markov chain modeling consists of two stages: (1) construction of transition-rates matrix called an infinitesimal generator and (2) calculation of steady-state probabilities.The first stage is a model specification. For a GJ gating model this could mean defining the states of a single gate and possible transitions among them, the number of gates in the GJ, and so forth. Basically, it results in formation of a transition matrixP, if one assumes a DTMC, or infinitesimal generator matrix Q, if one assumes CTMC. In this paper we consider mainly the CTMC models.Formation ofP and Q can be performed manually if the size of state space (n) is relatively small. For larger models the special software can be used, for example, methods based on events language [9], Petri nets [10], and stochastic automata networks [11].One of the main problems in Markov chain modeling of real systems is a rapid growth of the number of states. The number of states of the Markov chain grows exponentially, when the number of system components grows linearly. Therefore the use of efficient model creation tools and numerical methods is crucial [12].


### 2.2. Calculation of Steady-State Probabilities

The most difficult and time consuming part of Markov chain modeling is calculation of steady-state probabilities.Computation of steady-state probabilities of DTMC, which are stored as a row-vectorπ, is the solution of a system of linear equations:
(1)π·P=π.Similarly, computation of steady-state probabilities of DTMC, which are stored as a row-vectorπ, is the solution of a system of linear equations:
(2)π·Q=0,
where 0 denotes a zero row-vector of size n.Equations (1)-(2) can also be interpreted as computations of left side eigenvector corresponding to eigenvalue 1 (in case of DTMC) or eigenvalue 0 (in case of CTMC). Since P and Q are singular, an additional condition ∑i=1nπi=1 is used in all cases.There are three big classes of algorithms allowing evaluation of steady state probabilities: direct methods, iteration methods, and projection methods. More about numerical methods for solution of general linear systems can be found in [13]; more about application of numerical methods specifically for Markov chains is in [14].


### 2.3. Stochastic Automata Networks

SAN formalism [15] is one of the most efficient methods used to solve state-space explosion problem, which is very detrimental in Markov chain modeling. SAN allows very efficient construction and storage of infinitesimal generator Q by using tensor (Kronecker) algebra operations.Though SAN formalism originally was developed for the modeling of computer networks and communication systems [16, 17], there are multiple examples of SAN use in biology. For example, DeRemigio et al. [18] and Hao et al. [19] used SANs formalism to model calcium channels; Wolf [20] used SANs to describe kinetics of biochemical reactions.The main idea of SAN formalism is based on the division of a system into smaller subsystems, which can interact among themselves. Those subsystems are described by different stochastic automata. A single automaton is represented by a Markov chain, that is, by the set of subsystem states and possible transitions among them. If two (or more) automata somehow interact among themselves, then transition in one automaton may depend on the state of another one.The state of the whole system, so called global state, is a compositional state of all automata. An infinitesimal generator matrix of the whole system, so called global generator matrix, can be expressed by infinitesimal generators of individual automata and Kronecker algebra operations. We recall basic definitions below.Kronecker productA⊗B of two matrices A∈Rm×n and B∈Rp×q is given by
(3)A⊗B=a11B⋯a1nB⋮⋱⋮am1B⋯amnB∈Rmp×nq.Kronecker sumA⊕B of two squared matrices A∈Rm×m and B∈Rn×n is given by
(4)A⊕B=A⊗In+Im⊗B∈Rmn×mn,
where In, Im are identity matrices of sizes n and m, respectively. The Kronecker sum of more than two square matrices is also well defined [21].If the network consists ofk independent stochastic automata A(i), each governed by infinitesimal generators Q(i), i=1⋯k, then the global infinitesimal generator Q can be expressed as a tensor sum:
(5)Q=⨁i=1kQ(i).Expression (5) is also called the SAN descriptor of the system. For a SAN of independent automata steady-state probability, the vector π of the whole system is given by
(6)π=⨂i=1kπ(i),
where π(i) is a steady-state probability vector of an individual automaton A(i).If we are to consider a network, describing two independent gates that operate between open and closed states with transition ratesλoc and λco, then automata A(1) and A(2) model each hemichannel/gate, and each of them can be described using the infinitesimal generator:
(7)Q(1)=Q(2)=-λocλocλco-λco.Thus, the SAN descriptor of the network of two independent gates is given by(8)Q=Q1⊕Q2=Q1⊗I2+I2⊗Q2=-2λocλocλoc0λco-λco-λoc0λocλco0-λco-λocλoc0λcoλco-2λco.If automata in SAN are not completely independent, the interaction among them can also be expressed by the use of Kronecker algebra operations. Plateau expressed two different ways [15] to describe the interaction among automata.(1) Functional Transition Rates. A transition rate in a single automaton may depend on the state of the other automata, that is, on the global system state. Transition rates, which are independent on the global system state, are called constant transition rates.If we are to consider a network composed of 2 automata and suppose that the transition rates of each connexin depend on the number of connexins/subgates in the open state (denoted byno), then transition rates are functions: λoc=λocno and λco=λcono. Consequently, the SAN descriptor of the system is as follows:(9)Q=Q1⊕gQ2=-2λoc2λoc2λoc20λco1-λco1-λoc10λoc1λco10-λco1-λoc1λoc10λco0λco0-2λco0,where ⊕g denotes the generalized Kronecker product, which deals with functional transition rates [22].(2) Synchronizing Events. Transition in one automaton can cause transitions in other automata. Transition rates are called local, if they are not transition rates of synchronizing events. Synchronizing transitions may also be functional. In this paper, we do not use synchronizing events for the creation of gap junction models.Plateau and Atif showed that the SAN descriptor of a network consisting ofk automata and having l synchronizing events can be expressed as follows:
(10)Q=∑j=1k+2l⨂i=1gkQji.The use of SAN formalism basically solves matrix construction problems, since even large matrices can be built and stored (assuming there is enough storage space in operative memory) in a very short time.The main problem that arises when dealing with SANs of interacting automata is that the steady-state solution cannot be expressed as a simple product form (6). In this case, steady-state probabilities can be found either from solving (2) after Q is built from the SAN descriptor or directly from the descriptor. That is, building and storing of Q is not necessary, if special numerical methods are applied. It is possible not to build Q, since vector SAN descriptor product π∑j=1T⊗i=1NQji can be implemented efficiently, for example, by using shuffle algorithm. These problems are considered in detail in [23].


## 2.1. Markov Chain Modeling

We assume the stationary analysis of a homogenous irreducible Markov chain with a finite number of system states, denoted byn. Markov chain modeling consists of two stages: (1) construction of transition-rates matrix called an infinitesimal generator and (2) calculation of steady-state probabilities.The first stage is a model specification. For a GJ gating model this could mean defining the states of a single gate and possible transitions among them, the number of gates in the GJ, and so forth. Basically, it results in formation of a transition matrixP, if one assumes a DTMC, or infinitesimal generator matrix Q, if one assumes CTMC. In this paper we consider mainly the CTMC models.Formation ofP and Q can be performed manually if the size of state space (n) is relatively small. For larger models the special software can be used, for example, methods based on events language [9], Petri nets [10], and stochastic automata networks [11].One of the main problems in Markov chain modeling of real systems is a rapid growth of the number of states. The number of states of the Markov chain grows exponentially, when the number of system components grows linearly. Therefore the use of efficient model creation tools and numerical methods is crucial [12].


## 2.2. Calculation of Steady-State Probabilities

The most difficult and time consuming part of Markov chain modeling is calculation of steady-state probabilities.Computation of steady-state probabilities of DTMC, which are stored as a row-vectorπ, is the solution of a system of linear equations:
(1)π·P=π.Similarly, computation of steady-state probabilities of DTMC, which are stored as a row-vectorπ, is the solution of a system of linear equations:
(2)π·Q=0,
where 0 denotes a zero row-vector of size n.Equations (1)-(2) can also be interpreted as computations of left side eigenvector corresponding to eigenvalue 1 (in case of DTMC) or eigenvalue 0 (in case of CTMC). Since P and Q are singular, an additional condition ∑i=1nπi=1 is used in all cases.There are three big classes of algorithms allowing evaluation of steady state probabilities: direct methods, iteration methods, and projection methods. More about numerical methods for solution of general linear systems can be found in [13]; more about application of numerical methods specifically for Markov chains is in [14].


## 2.3. Stochastic Automata Networks

SAN formalism [15] is one of the most efficient methods used to solve state-space explosion problem, which is very detrimental in Markov chain modeling. SAN allows very efficient construction and storage of infinitesimal generator Q by using tensor (Kronecker) algebra operations.Though SAN formalism originally was developed for the modeling of computer networks and communication systems [16, 17], there are multiple examples of SAN use in biology. For example, DeRemigio et al. [18] and Hao et al. [19] used SANs formalism to model calcium channels; Wolf [20] used SANs to describe kinetics of biochemical reactions.The main idea of SAN formalism is based on the division of a system into smaller subsystems, which can interact among themselves. Those subsystems are described by different stochastic automata. A single automaton is represented by a Markov chain, that is, by the set of subsystem states and possible transitions among them. If two (or more) automata somehow interact among themselves, then transition in one automaton may depend on the state of another one.The state of the whole system, so called global state, is a compositional state of all automata. An infinitesimal generator matrix of the whole system, so called global generator matrix, can be expressed by infinitesimal generators of individual automata and Kronecker algebra operations. We recall basic definitions below.Kronecker productA⊗B of two matrices A∈Rm×n and B∈Rp×q is given by
(3)A⊗B=a11B⋯a1nB⋮⋱⋮am1B⋯amnB∈Rmp×nq.Kronecker sumA⊕B of two squared matrices A∈Rm×m and B∈Rn×n is given by
(4)A⊕B=A⊗In+Im⊗B∈Rmn×mn,
where In, Im are identity matrices of sizes n and m, respectively. The Kronecker sum of more than two square matrices is also well defined [21].If the network consists ofk independent stochastic automata A(i), each governed by infinitesimal generators Q(i), i=1⋯k, then the global infinitesimal generator Q can be expressed as a tensor sum:
(5)Q=⨁i=1kQ(i).Expression (5) is also called the SAN descriptor of the system. For a SAN of independent automata steady-state probability, the vector π of the whole system is given by
(6)π=⨂i=1kπ(i),
where π(i) is a steady-state probability vector of an individual automaton A(i).If we are to consider a network, describing two independent gates that operate between open and closed states with transition ratesλoc and λco, then automata A(1) and A(2) model each hemichannel/gate, and each of them can be described using the infinitesimal generator:
(7)Q(1)=Q(2)=-λocλocλco-λco.Thus, the SAN descriptor of the network of two independent gates is given by(8)Q=Q1⊕Q2=Q1⊗I2+I2⊗Q2=-2λocλocλoc0λco-λco-λoc0λocλco0-λco-λocλoc0λcoλco-2λco.If automata in SAN are not completely independent, the interaction among them can also be expressed by the use of Kronecker algebra operations. Plateau expressed two different ways [15] to describe the interaction among automata.(1) Functional Transition Rates. A transition rate in a single automaton may depend on the state of the other automata, that is, on the global system state. Transition rates, which are independent on the global system state, are called constant transition rates.If we are to consider a network composed of 2 automata and suppose that the transition rates of each connexin depend on the number of connexins/subgates in the open state (denoted byno), then transition rates are functions: λoc=λocno and λco=λcono. Consequently, the SAN descriptor of the system is as follows:(9)Q=Q1⊕gQ2=-2λoc2λoc2λoc20λco1-λco1-λoc10λoc1λco10-λco1-λoc1λoc10λco0λco0-2λco0,where ⊕g denotes the generalized Kronecker product, which deals with functional transition rates [22].(2) Synchronizing Events. Transition in one automaton can cause transitions in other automata. Transition rates are called local, if they are not transition rates of synchronizing events. Synchronizing transitions may also be functional. In this paper, we do not use synchronizing events for the creation of gap junction models.Plateau and Atif showed that the SAN descriptor of a network consisting ofk automata and having l synchronizing events can be expressed as follows:
(10)Q=∑j=1k+2l⨂i=1gkQji.The use of SAN formalism basically solves matrix construction problems, since even large matrices can be built and stored (assuming there is enough storage space in operative memory) in a very short time.The main problem that arises when dealing with SANs of interacting automata is that the steady-state solution cannot be expressed as a simple product form (6). In this case, steady-state probabilities can be found either from solving (2) after Q is built from the SAN descriptor or directly from the descriptor. That is, building and storing of Q is not necessary, if special numerical methods are applied. It is possible not to build Q, since vector SAN descriptor product π∑j=1T⊗i=1NQji can be implemented efficiently, for example, by using shuffle algorithm. These problems are considered in detail in [23].


## 3. Results and Discussion

In this section, we present CTMC models of GJs, created by using SAN formalism. The structure of infinitesimal generators and efficient application of numerical methods for steady-state solutions are considered in detail.


### 3.1. CTMC Model of the GJ Channel Containing the 12 Two-State Subgates

Gap junctions form clusters (junctional plaques) of individual channels arranged in parallel in the junctional membrane of two adjacent cells. The GJ channel is composed of 2 hemichannels (left and right) arranged in series. Each hemichannel is composed/oligomerized from six Cxs forming a hexamer with the pore inside. We envision that each hemichannel forms the gate, which is composed of six subgates arranged in parallel; that is, to each connexin the subgate is attributed and the GJ channel ultimately contains two gates composed of 12 subgates (see Figure1).Figure 1
Electrical scheme of the GJ channel composed of two hemichannels each formed of 6 connexins. Transjunctional voltage (Vj) controls both hemichannels and all Cxs can operate between open and closed (and deep closed) states.In this section, we will consider a model, in which each subgate operates between open (o) and closed (c) states (see Figure 2), with transition rates λoc (from o to c) and λco (from c to o).Figure 2
Two-state transition graph of a subgate.One of the most important steps of SAN model creation is to decide which part of a system to model by an individual automaton. In this case it is possible to describe each subgate as an individual automaton with two states. This would result in SAN of 12 automata with 212 = 4096 states.However, it is unnecessary to track each subgate individually; since all subgates are identical thenVj-gating depends on the number of open and closed gates in each hemichannel. Thus, much more convenient way is to describe the whole hemichannel as an individual automaton, whose states denote the number of closed (or open) subgates in hemichannel.Thus we model the GJ channel by two automata—an automatonA2l, which describes the left hemichannel, and A2(r), which describes the right hemichannel (number 2 in the subscript denotes the fact, that each subgate has two possible states).We assume that both automata have 7 possible states, which denote the number of closed subgates in each hemichannel (i.e., it can be denoted by0,1,…,6).Thus, automatonA2l can leave a state nlnl=1,6¯ and enter a state nl-1 with transition rate nl·λco. Similarly, it can leave state nlnl=0,5¯ and go to the state nl+1 with transition rate 6-nl·λoc.Thus an infinitesimal generatorQ2l of automaton A2l is as follows:
(11)Q2l=*6λoc00000λco*5λoc000002λco*4λoc000003λco*3λoc000004λco*2λoc000005λco*λoc000006λco*,
where diagonal entries (denoted by *) are equal to the negated sum of the nondiagonal entries in that row.It is crucial to emphasize that transition rates of the matrixQ2l in (11) depend on the voltage across the left and right hemichannels, which accordingly depends on the number of closed (open) gates:
(12)λoc=λocVleftnl,Vrightnr,λco=λcoVleftnl,Vrightnr.Since both hemichannels are identical, an infinitesimal generator of the right hemichannel is the same; that is,Q2l=Q2r. In this case, global infinitesimal generator of the GJ, which we denote by Q212, may be written as
(13)Q212=Q2l⊕gQ2r=Q2l⊗gI7+I7⊗gQ2r.Since bothQ2l and Q2r are tridiagonal matrices, it follows from (13) that Q212 is a block tridiagonal matrix. It consists of 49 square blocks, each of size 7 and can be written as follows:
(14)Q212=Q11Q1200000Q21Q22Q2300000Q32Q33Q3400000Q43Q44Q4500000Q54Q55Q5600000Q65Q66Q7600000Q76Q77.
Here 0 denote square zero matrix blocks of size 7.SinceQ2l and Q2r are tridiagonal matrices, then from (14) it follows that diagonal blocks Qii are the following tridiagonal matrices:
(15)Qii=-i-1λco+7-iλocI7+Q2r,i=1,7¯.
Here λco=λco(Vleft7-i,Vrightj) and j is the row in a block Qii, in which transition rate λco appears. Similarly, λoc=λoc(Vleft7-i,Vrightj) and j is the row in a block Qii, in which λoc appears.Similarly, upper subdiagonal blocks inQi+1,i may be written as follows:
(16)Qi,i+1=7-iλocI7,i=1,6¯,
where λoc=λoc(Vleft7-i,Vrightj) and j is therow in a block Qi,i+1, in which λoc appears.And finally, lower subdiagonal blocks in (14) are as follows:
(17)Qi+1,i=i-1λcoI7,i=2,7¯,
where λco=λco(Vlefti+1,Vrightj) and j is the row in a block Qi,i+1, in which λco appears.


### 3.2. Evaluation of Functional Transition Rates

As we mentioned in a previous chapter, all transition rates in GJ voltage gating model are functional. Therefore, each transition changes the number of closed (open) gates, which changes the conductance and voltage across the channel accordingly, thus changing the values of transition rates. These changes depend on gating parameters of subgates; in homotypic GJ channels they are identical for all 12 subgates.Even though these formulas were published earlier [6], we present them here, since they demonstrate the complexity of functional transition rates using SAN modeling of GJ.In the DTMC model, probabilities of two-state gate transitions can be described as follows:(18)pocA,P,Vleftright,V0=K·kA,P,Vleftright,V01+kA,P,Vleftright,V0,pcoA,P,Vleftright,V0=K1+kA,P,Vleftright,V0.In (18), k is
(19)kP,Vleftright,V0=eA·P·Vleftright-V0,
where P is a gating polarity (+1 or −1); A (1/mV) is a coefficient characterizing gating sensitivity to voltage; K is a constant used to change kinetics of c↔o transitions (K can accelerate or decelerate c↔o transitions but does not affect conditions of the steady-state); Vo (mV) is a voltage across the hemichannel/connexin at which probabilities for o and c states are equal; Vleft/right is variable voltage across the left or right subgate (mV).DTMC probabilities can be transformed into transition rates of CTMC by the following equation:(20)λoc=pocτ,λco=pcoτ,
where τ is a short period of time, in which the probability to observe multiple transitions is negligible; that is, for i≠j, pijτ→0 if τ→0.Each subgate, depending on a voltage across it (Vleft/right), can gate/operate by changing stepwise between the open state with conductance go and the closed state with conductance gc. It was assumed that go and gc values exhibit rectification, that is, depend on Vleft/right exponentially:
(21)goVleftright,P=2·exp⁡P·VleftrightRo,gcVleftright,P=0.25·exp⁡P·VleftrightRc,
where Vleft/right is a voltage across the left or right hemichannel, while Ro and Rc are rectification constants.The conductance of the left hemichannel, whennl Cxs are closed, can be described as follows:
(22)gleftnl=nlgcVleftnl,P+6-nlgoVleftnl,P.Similarly, the conductance of the right hemichannel, whennr Cxs are closed, is
(23)grightn=nrgcVrightn,P+6-nrgoVrightn,P.During gating, conductance of subgates ranges betweengo(Vleftright,P) and gc(Vleftright,P), and the total conductance of the GJ channel can be found using steady-state probabilities of Markov-chain model:
(24)g=∑iπigleftVleftnl·grightVrightnrgleftVleftnl+grightVrightnr,
where πi is a steady-state probability for nl Cxs in the left hemichannel and nr Cxs in the left hemichannel to be closed.Conductance of the GJ channel depends on the voltage; that is, the circuit is nonlinear. In order to calculate voltage across each Cx, we used an iterative procedure [7]. We assumed that the value of voltage is settled, if a difference between voltage values, calculated at two consecutive iterations, is less than 0.1 percent. Calculation showed that at least 5 iterations were needed to achieve the aforesaid precision.As one can see, the evaluation of functional transition rates of SAN model is not a trivial task in this case. SAN formalism allows estimating steady-state probabilities directly from SAN descriptor but not building and storing infinitesimal generator, for example, by using shuffle algorithm. However, there would be a necessity to evaluate functional transition rates during each iteration for evaluation of steady-state probabilities. Thus, it would require too much CPU time in case of GJ models. Moreover, the number of system states of GJ models presented in this paper is relatively small; therefore we use the different approach. We apply SAN formalism to specify the system behaviour and to create equivalent Markov chain model. The use of Kronecker algebra representation of global infinitesimal generator helps to get the insight of matrix structure and to apply numerical methods for evaluation of a steady-state solution.


### 3.3. Numerical Solution of Two-State CTMC Models of the GJ Channel Containing 12 Two-State Subgates

It follows from (16)-(17) that subdiagonal blocks in (14) are diagonal matrices. These properties allow using numerical methods for the calculation of steady-state probabilities and we consider three algorithms for steady-state solution in detail: banded Gaussian elimination, direct solution by recursion, and block Gauss-Seidel methods.


#### 3.3.1. Banded Gaussian Elimination for Steady-State Solution of the CTMC Model of GJ Channel Containing 12 Two-State Subgates

A square matrixQ=qij is called banded if its entries are zero outside of the diagonally bordered band, which can be described by the following equation:
(25)qij=0,ifj<i-k1orj>i+k2.In (25), numbers k1 and k2 are called left and right half-bandwidths, respectively. The bandwidth of the matrix m is equal to (k1+k2+1). For example, a matrix with k1=k2=1 is tridiagonal matrix, that is, matrix with bandwidth 3.Complexity. If a matrix has bandwidth m, a more efficient implementation of Gaussian elimination exists than the standard one, which has a complexity of O(n3). The solution of the linear system with bandwidth m has an approximate complexity of O(m2n). To be exact, the complexity of banded Gaussian elimination is nm+12/4, while it is (4n3+9n2-13n)/6 for standard Gaussian elimination [24].From (14) it follows that Q has bandwidth m=15. Thus, it requires approximately 13 times less CPU time to apply banded Gaussian elimination to solve an equivalent DTMC model, which has a dense transition probability matrix.


#### 3.3.2. Recursive Method for Steady-State Solution of CTMC Model of GJ Channel Containing 12 Two-State Subgates

An algorithm similar to the Thomas algorithm for tridiagonal matrices can be used to calculate steady-state probabilities of the GJ model. We use the matrix form of solution technique as presented in [14]. Infinitesimal generator Q can be divided into four blocks as follows:
(26)Vl=Q11Q210000T,X=0,Y=0000Q76Q77,W=Q1200000Q22Q230000Q32Q33Q340000Q43Q44Q450000Q54Q55Q560000Q65Q66Q67.Dividing vectorπ into segments, solution of
(27)π*π7VWXY=0
can be implemented by solving π7YW-1V=0 in two steps. At first, solving WZ=V for Z gives W-1V, while YZ gives coefficient matrix for solving π7. After that, the remaining part π* of steady-state vector π can be found from π*W=π7Y.Complexity. The procedure for obtaining a recursive solution can be implemented very efficiently due to the structure of the infinitesimal generator Q. For example, computation of Z is basically a backward substitution, since W is lower triangular. Also, finding the inverse of subdiagonal blocks is a trivial task, since these blocks are diagonal matrices.Since the size of state-spacen is not large for this Markov model, an approximate complexity evaluation by using big O notation might be too general in this case. Therefore, we evaluated the amount of operations necessary to implement the recursive procedure in more detailed way. We distinguished 6 types of distinct operations (e.g., matrix summation, matrix multiplication, etc.) adapted to different types of operands, such as dense matrix and tridiagonal matrix. A conservative estimation of number of arithmetic operations is presented in Table 1. We assume that these operations are implemented in the most basic way (e.g., we use cij=∑i=1naikbkj for matrix multiplication C=AB).Table 1
Evaluation of the number of arithmetic operations necessary to implement the recursive procedure for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Matrix + matrix
11
n
2
Matrix * matrix
6
n
3 − n2
Matrix * diagonal matrix
13
n
2
Vector * diagonal matrix
6
n
Vector * tridiagonal matrix
7
5
n
Solve dense system
1
(4n3 + 9n3 − 13n3)/6Detailed evaluation showed that recursive solution requires about 1.8 times less CPU time than banded Gaussian elimination and at least 23 times less than standard Gaussian elimination.Stability. The main problem of the block recursive procedure is numerical stability, due to rounding errors [14]. However, these problems are mitigated by the fact that matrix entries are relatively small (in the range of 0.001–0.01).We compared the solution provided by the recursive procedure with the solution calculated using a stable numerical method. Experimental data showed that steady-state probabilities obtained by the recursive procedure differ less than 10−12 from an exact solution for this particular GJ model.


#### 3.3.3. Block Gauss-Seidel Method for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Two-State Subgates

The block Gauss-Seidel method is an iterative technique and thus eliminates stability concerns completely [14]. It can also be implemented very efficiently for block tridiagonal matrices.If solution vectorπ is divided according to the block structure of Q, then at k+1 outer iteration it is required to solve 7 inner iterations, which may be written as follows:
(28)π1k+1=-π2kQ21Q11-1;πik+1=-πi-1k+1Qi-1,1+πi+1kQi+1,1Q11-1,i=2,6¯;π7k+1=-π6k+1Q67Q77-1.Complexity. In this case, diagonal blocks are tridiagonal matrices and the linear system solution has a complexity of O(n). The number of operations (including a proof for convergence) necessary to perform a single outer iteration is presented in Table 2.Table 2
Number of arithmetic operations necessary to implement a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
5
n
Vector * tridiagonal matrix
12
5n
Solve tridiagonal system
7
8n
Check for convergence
1
nThe efficiency of the whole algorithm depends on convergence speed. That is, block Gauss-Seidel method would be more efficient than the recursive procedure if it required 4 or less iterations. Similarly, it would be more efficient than banded Gaussian elimination if the number of outer iterations was less than 7, and, finally, it would be more efficient than standard Gaussian elimination if block Gauss-Seidel required less than 96 outer iterations.We evaluated the number of outer iterations necessary to find a steady-state solution of the GJ model containing 12 two-state gates atVj=40 mV. Each time an initial iteration vector was chosen as a standard vector with equal entries, that is, each entry equal to 1/n. We assumed that necessary precision ε is achieved if the following condition was satisfied:
(29)max⁡iπik+1-πik<ε.Inequality (29) means that all entries of consecutive iterations differ less than ε in absolute value. The results of a convergence are presented in Table 3.Table 3
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Precision
Number of iterations
1
0
-
4
15
1
0
-
5
18
1
0
-
6
20
1
0
-
7
23
1
0
-
8
25
1
0
-
9
28
1
0
-
10
31
1
0
-
11
33
1
0
-
12
36
1
0
-
13
39
1
0
-
14
41
1
0
-
15
44Thus, for this particular GJ model the block Gauss-Seidel method is more efficient than standard Gaussian elimination at any precision level. However it is less efficient than the direct methods, for example, banded Gaussian algorithm or the recursive procedure presented in Section3.3.2.In addition, modification of the block Gauss-Seidel method outperformed other standard iterative algorithms (Jacobi, Gauss-Seidel) as well as projection methods (Arnoldi, GMRES, and BiCGSTAB). While the convergence of the fastest of projection methods, BiCGSTAB, was slightly better than that of block Gauss-Seidel, overall CPU time was longer (about 18 percent), since it required more time to perform a single iteration.


#### 3.3.4. Repetitive Model Solution

Moreover, since the block Gauss-Seidel method is an iterative technique, it can be implemented more efficiently for repetitive solutions, which are especially important in the search for optimal model parameters. Iterative methods have an advantage over direct methods, since the previous solution vector can be used as a starting point for the solution of model with different set of parameters.A solution of the model at differentVj values can be described using Pseudocode 1.Pseudocode 1
(1)Q(1) ←FormInfinitesimalGenerator(V1);
(2)it ←SetInitialIterationVector();
(3)π(1) ←SteadyStateSolution(Q(1), it);
(4)C1 ←EstimateGJConductance(π(1));
(5) fori = 2 to k do
Q(i) ←FormInfinitesimalGenerator(Vi);
π(i) ←SteadyStateSolution(Q(i), π(i-1));
C1 ←EstimateGJConductance(π(i));
end   for.A similar procedure can be applied not only at differentVjs, but also with other gating parameters as well.It is known [25] that the difference between steady-state solutions of two linear systems, Q·π=0 and Q+ΔQ·π+Δπ=0, is constrained by the following relationship between norms of matrices and vectors:
(30)Δππ≤Q#·ΔQ;Q# is group inverse of infinitesimal generator Q.Thus, steady-state vectorsπi are relatively close to each other if matrices Q and Q+ΔQ are close and Q# is not large.Simulation ofVj-gating partially satisfies aforementioned conditions, since changes of entries of Q are in the range of 0.0001–0.001 due to the voltage change from 40 mV to 41 mV, while the norm Q# is equal to 213.73 at 40 mV level.In order to evaluate an effect of iterative methods for the repetitive model solution, more detailed experimental research was performed. We changed voltage across GJ channel from 0 to 100 mV by 0.1 mV intervals. Thus, 1000 different infinitesimal generators were built and the steady-state solution was calculated according to a scheme presented in Pseudocode1. Firstly, we used standard iteration vector with equal entries each time (we will refer to it as “Method I”), while for the second round of calculation a previous steady-state solution was used each time, as presented in Pseudocode 1 (we will refer to it as “Method II”). We evaluated the number of outer iterations necessary to achieve 10−6 precision for both cases. The results are presented in Table 4.Table 4
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
15
6
40
20
10
60
26
16
80
19
11
100
11
5A positive effect of “Method II” is obvious. The number of outer iterations decreases from about 30 to 60 percent depending onVj level. Overall, it required about 38 percent less CPU time to perform calculations by using “Method II” instead of “Method I.” CPU time in this case was comparable to that of banded Gaussian elimination.


### 3.4. CTMC Model of the GJ Channel Containing 6 Three-State Gates

We assume that in this GJ model only subgates in the left hemichannel operate [4], while subgates in the right hemichannel are always open (see Figure 3).Figure 3
Electrical scheme of the GJ channel composed of two hemichannels each formed of 6 connexins/subgates.Vj influence both hemichannels but only Cxs on the left operate between open, closed, and deep closed states, while Cxs on the right are always open.We also assume that each subgate operates between open (o), closed (c), and deep-closed (d) states. The transition among these states is presented in Figure 4.Figure 4
Three-state transition graph of a subgate.In this case our SAN model consists of a single automatonA3l (subscript value 3 denotes that each subgate has 3 possible states), which describes the left hemichannel. If we assume that states of the left hemichannel are numbers of open and closed gates, denoted by no and nc, respectively, then the state-space of a system consists of 2-tuples (no,nc) satisfying the following inequality:
(31)no+nc≤6.It follows from (31) that the state-space has the size of 28. From a state no,nc automaton can go to the state no+1,nc-1 with transition rate nc·λco; to the state no-1,nc+1 with transition rate no·λoc; to the state no,nc+1 with transition rate 6-no-nc·λdc; and finally to the state no,nc-1 with transition rate nc·λcd.An infinitesimal generatorQ3l of the left hemichannel (as well as the global system generator, i.e., Q3l=Q36) has the same block tridiagonal structure as in (14):
(32)Q36=Q11Q1200000Q21Q22Q2300000Q32Q33Q3400000Q43Q44Q4500000Q54Q55Q5600000Q65Q66Q7600000Q76Q77.However, all the blocks in (32) including zero-entry blocks are of varying sizes. In general, block entry ij of the infinitesimal generator is of size 8-i×8-j. For example, diagonal blocks Qii are square matrices of size 8-i each and have the following tridiagonal form:
(33)Qii=*7-iλdc⋮00λcd*⋮0002λcd⋮00⋯⋯⋱⋯⋯00⋮2λdc000⋮*λdc00⋮7-iλcd*,
where λdc=λdc(Vleftno,nc)=λdc(Vlefti,j) and λcd=λcd(Vleftno,nc)=λcd(Vlefti,j) and j is the row in a block Qii where λdc or λcd appears.All upper diagonal blocksQi,i+1 have the following structure (zero-entries row vector augmented with diagonal matrix):
(34)Qi,i+1=00⋮0λco0⋮002λco⋯0⋮⋮⋮000⋮7-iλco,
where λco=λco(Vleftno,nc)=λco(Vlefti-1,j-1) and j is the row in a block Qi,i+1 where λco appears.Similarly, lower diagonal blocksQi+1,i are diagonal matrices augmented with a zero-entry column and may be written as follows:
(35)Qi+1,i=0i-1λoc0⋮000i-1λoc⋮0⋯⋯⋯⋱⋯000⋮i-1λoc,
where λoc=λoc(Vleftno,nc)=λoc(Vlefti-1,j-1) and j is the row in a block Qi+1,i, where λco appears.The first problem arising in steady-state calculation is that the blocks are of different sizes. It means that the recursive procedure, which was most efficient for GJ models with 12 two-state Cxs, cannot be applied in this case. This leaves only banded Gaussian elimination and block Gauss-Seidel methods for further detailed consideration.


#### 3.4.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Subgates

It is easy to see from (32) that Q36 has the same bandwidth m=15 as Q212 but the size of state-space n=28 is different, in this case. So, according to the complexity evaluation presented in [24], the steady-state solution by using banded Gaussian elimination requires only about 4-fold less CPU time than standard Gaussian elimination for dense linear system. Thus, the difference is not as pronounced as in the previous example.


#### 3.4.2. Block Gauss-Seidel Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Gates

The application of block Gauss-Seidel is very similar to that for GJ model with 12 two-state Cxs. Basically, the same iterative procedure (28) can be applied; however blocks are of different sizes in this case. Thus, even though the same basic operations with the same complexity as presented in Table 2 are used for this model, one must evaluate varying sizes of blocks in the matrix Q36. For example, instead of solving 7 tridiagonal systems, each of size 7, one needs only to solve one system of size 7, one of size 6, and so forth.This gives an estimated complexity of 196 per single outer iteration with the block Gauss-Seidel method. Thus, block Gauss-Seidel outperforms standard Gaussian elimination if less than 80 outer iterations are needed. It also outperforms banded Gaussian elimination if less than 18 outer iterations are needed.As for the 12 two-state Cxs GJ model, we evaluated the number of outer iterations necessary to achieve required precision. The convergence speed is presented in Table5.Table 5
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
20
1
0
-
6
25
1
0
-
7
30
1
0
-
8
35
1
0
-
9
40
1
0
-
10
45
1
0
-
11
50
1
0
-
12
56
1
0
-
13
61
1
0
-
14
66
1
0
-
15
71Thus, it is less feasible to use block Gauss-Seidel method than banded Gaussian elimination if higher than 10−5 precision is used, though it is more efficient than standard Gaussian elimination even with 10−15 precision.However, the efficiency of block Gauss-Seidel becomes higher if the repetitive model solution is performed. A similar experiment as with the 12 two-state Cxs model was performed for 6 three-state subgates GJ model. The results are presented in Table6.Table 6
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
12
7
40
18
15
60
20
9
80
14
4
100
12
3The results showed that block Gauss-Seidel becomes more efficient than banded Gaussian elimination under reasonable 10−6 precision if repetitive calculations are performed.


### 3.5. CTMC Model of the GJ Channel Containing 12 Three-State Subgates

Here, we consider that in the model each subgate of both hemichannels operates between open (o), closed (c), and deep closed (d) states. Thus, its electrical scheme is the same as presented in Figure 1, while the state graph of the subgate is as presented in Figure 3.We model this type of GJ by SAN, containing two automata. We assume thatA3l describes the left hemichannel, while A3r describes the right one (again, subscript values 3 denote the fact that each subgate has 3 possible states). The states of both automata A3l and A3r are 2-tuples nol,ncl and nor,ncr, respectively. Here nol and ncl denote the number of open and closed subgates on the left hemichannel, while nor and ncr denote the number of closed and open gates on the right one. They also must satisfy the following inequalities:
(36)nol+ncl≤6,nor+ncr≤6.Transitions among states in each hemichannel are analogous to those of the previous model. Similarly, infinitesimal generatorsQ3l and Q3r can be written as in (32). Thus global infinitesimal generator Q312 may be expressed as
(37)Q312=Q3l⊗gI28+I28⊗gQ3r.It is easy to see from (37) that Q312 has the size of 748; thus it is a much larger model than in previous examples. It is not possible due to the size of the matrix to present its full block structure. However, its nonzero entry structure, which was obtained by usingspy() function from MATLAB package, is presented in Figure 5.Figure 5
Nonzero entry structure of global system generatorQ312 of GJ channel composed of two hemichannels formed of 6 connexins with 3 states.It is also possible to analyze its structure based on the Kronecker representation of system descriptor (37). As can be seen from Figure 5, it consists of 5 layers of blocks, all of which are square matrices of size 28. Diagonal blocks Qii are all block tridiagonal matrices, which may be written as follows:
(38)Qii=qii⊗I7+Q36.
Here qii denotes the ith diagonal entry of the matrix Q36.It follows from (38) that Qii has the same nonzero entries structure as Q36. Matrix Q312 also has two layers of blocks in lower and upper parts. For simplicity, we call them inside-lower (inside-upper) and outside-lower (outside-upper) layers. All of these blocks are diagonal matrices and can be written as
(39)Qij=qij⊗I28,
where qij denotes the ijth entry of matrix Q36.Since matrixQ312 is not tridiagonal, it leaves banded Gaussian elimination and block Gauss-Seidel methods for more detailed consideration.


#### 3.5.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Even though matrix (38) is banded, its bandwidth 393 is much bigger in both absolute and relative (m exceeds half of the size of n) values than that of 12 two-state Cxs GJ model. It requires about 5 times less CPU time than standard Gaussian elimination to calculate steady-state probabilities.


#### 3.5.2. Block Gauss-Seidel Algorithm for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Analyzing the zero-entries structure of (38) allows for adaptation of the block Gauss-Seidel algorithm for Q312 model. Basically, in one outer iteration step one needs to solve 28 inner iterations—each of them is a linear system of size 28:
(40)πik+1=bQii-1,i=1,28¯,
where row vector b might consist of up to four vectors of form πrk+1Ql,m or πrkQl,m. In general, the number of arithmetic operations necessary to perform one outer iteration of the block Gauss-Seidel algorithm for Q312model is presented in Table 7 (size n in this case is equal to 28).Table 7
Number of operations necessary to perform a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
56
n
Vector * diagonal matrix
84
n
Solve tridiagonal system
28
8
n
Check for convergence
1
nThus, the block Gauss-Seidel algorithm becomes more efficient than standard Gaussian elimination if it requires less than 5954 outer iterations. Actual numbers of outer iterations necessary to achieve the required precision at 40 mV transjunctional voltage level are presented in Table8.Table 8
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
23
1
0
-
6
32
1
0
-
7
40
1
0
-
8
49
1
0
-
9
58
1
0
-
10
66
1
0
-
11
75
1
0
-
12
83
1
0
-
13
92
1
0
-
14
101
1
0
-
15
109Basically the convergence speed of block Gauss-Seidel for solving steady-state probabilities of the 12 three-state subgates GJ model is comparable to that of previous models. Also, block Gauss-Seidel is much more efficient than even banded Gaussian elimination with any precision. As in previous cases, it outperformed other standard iterative and projection methods.For example, it required less than 40 milliseconds of CPU time to calculate steady-state probabilities with 10−6 precision with MATLAB while its implementation in C++ required about 18 milliseconds.The repetitive model solution showed the same effect of iterative algorithms on convergence speed as in previous examples. The results are presented in Table9.Table 9
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
24
15
40
32
25
60
30
23
80
18
8
100
12
3Overall, about 40 percent less CPU time was required to estimate steady-state probabilities in the whole range of transjunctional voltage by using, if previous solutions were used as the first iteration vector.


## 3.1. CTMC Model of the GJ Channel Containing the 12 Two-State Subgates

Gap junctions form clusters (junctional plaques) of individual channels arranged in parallel in the junctional membrane of two adjacent cells. The GJ channel is composed of 2 hemichannels (left and right) arranged in series. Each hemichannel is composed/oligomerized from six Cxs forming a hexamer with the pore inside. We envision that each hemichannel forms the gate, which is composed of six subgates arranged in parallel; that is, to each connexin the subgate is attributed and the GJ channel ultimately contains two gates composed of 12 subgates (see Figure1).Figure 1
Electrical scheme of the GJ channel composed of two hemichannels each formed of 6 connexins. Transjunctional voltage (Vj) controls both hemichannels and all Cxs can operate between open and closed (and deep closed) states.In this section, we will consider a model, in which each subgate operates between open (o) and closed (c) states (see Figure 2), with transition rates λoc (from o to c) and λco (from c to o).Figure 2
Two-state transition graph of a subgate.One of the most important steps of SAN model creation is to decide which part of a system to model by an individual automaton. In this case it is possible to describe each subgate as an individual automaton with two states. This would result in SAN of 12 automata with 212 = 4096 states.However, it is unnecessary to track each subgate individually; since all subgates are identical thenVj-gating depends on the number of open and closed gates in each hemichannel. Thus, much more convenient way is to describe the whole hemichannel as an individual automaton, whose states denote the number of closed (or open) subgates in hemichannel.Thus we model the GJ channel by two automata—an automatonA2l, which describes the left hemichannel, and A2(r), which describes the right hemichannel (number 2 in the subscript denotes the fact, that each subgate has two possible states).We assume that both automata have 7 possible states, which denote the number of closed subgates in each hemichannel (i.e., it can be denoted by0,1,…,6).Thus, automatonA2l can leave a state nlnl=1,6¯ and enter a state nl-1 with transition rate nl·λco. Similarly, it can leave state nlnl=0,5¯ and go to the state nl+1 with transition rate 6-nl·λoc.Thus an infinitesimal generatorQ2l of automaton A2l is as follows:
(11)Q2l=*6λoc00000λco*5λoc000002λco*4λoc000003λco*3λoc000004λco*2λoc000005λco*λoc000006λco*,
where diagonal entries (denoted by *) are equal to the negated sum of the nondiagonal entries in that row.It is crucial to emphasize that transition rates of the matrixQ2l in (11) depend on the voltage across the left and right hemichannels, which accordingly depends on the number of closed (open) gates:
(12)λoc=λocVleftnl,Vrightnr,λco=λcoVleftnl,Vrightnr.Since both hemichannels are identical, an infinitesimal generator of the right hemichannel is the same; that is,Q2l=Q2r. In this case, global infinitesimal generator of the GJ, which we denote by Q212, may be written as
(13)Q212=Q2l⊕gQ2r=Q2l⊗gI7+I7⊗gQ2r.Since bothQ2l and Q2r are tridiagonal matrices, it follows from (13) that Q212 is a block tridiagonal matrix. It consists of 49 square blocks, each of size 7 and can be written as follows:
(14)Q212=Q11Q1200000Q21Q22Q2300000Q32Q33Q3400000Q43Q44Q4500000Q54Q55Q5600000Q65Q66Q7600000Q76Q77.
Here 0 denote square zero matrix blocks of size 7.SinceQ2l and Q2r are tridiagonal matrices, then from (14) it follows that diagonal blocks Qii are the following tridiagonal matrices:
(15)Qii=-i-1λco+7-iλocI7+Q2r,i=1,7¯.
Here λco=λco(Vleft7-i,Vrightj) and j is the row in a block Qii, in which transition rate λco appears. Similarly, λoc=λoc(Vleft7-i,Vrightj) and j is the row in a block Qii, in which λoc appears.Similarly, upper subdiagonal blocks inQi+1,i may be written as follows:
(16)Qi,i+1=7-iλocI7,i=1,6¯,
where λoc=λoc(Vleft7-i,Vrightj) and j is therow in a block Qi,i+1, in which λoc appears.And finally, lower subdiagonal blocks in (14) are as follows:
(17)Qi+1,i=i-1λcoI7,i=2,7¯,
where λco=λco(Vlefti+1,Vrightj) and j is the row in a block Qi,i+1, in which λco appears.


## 3.2. Evaluation of Functional Transition Rates

As we mentioned in a previous chapter, all transition rates in GJ voltage gating model are functional. Therefore, each transition changes the number of closed (open) gates, which changes the conductance and voltage across the channel accordingly, thus changing the values of transition rates. These changes depend on gating parameters of subgates; in homotypic GJ channels they are identical for all 12 subgates.Even though these formulas were published earlier [6], we present them here, since they demonstrate the complexity of functional transition rates using SAN modeling of GJ.In the DTMC model, probabilities of two-state gate transitions can be described as follows:(18)pocA,P,Vleftright,V0=K·kA,P,Vleftright,V01+kA,P,Vleftright,V0,pcoA,P,Vleftright,V0=K1+kA,P,Vleftright,V0.In (18), k is
(19)kP,Vleftright,V0=eA·P·Vleftright-V0,
where P is a gating polarity (+1 or −1); A (1/mV) is a coefficient characterizing gating sensitivity to voltage; K is a constant used to change kinetics of c↔o transitions (K can accelerate or decelerate c↔o transitions but does not affect conditions of the steady-state); Vo (mV) is a voltage across the hemichannel/connexin at which probabilities for o and c states are equal; Vleft/right is variable voltage across the left or right subgate (mV).DTMC probabilities can be transformed into transition rates of CTMC by the following equation:(20)λoc=pocτ,λco=pcoτ,
where τ is a short period of time, in which the probability to observe multiple transitions is negligible; that is, for i≠j, pijτ→0 if τ→0.Each subgate, depending on a voltage across it (Vleft/right), can gate/operate by changing stepwise between the open state with conductance go and the closed state with conductance gc. It was assumed that go and gc values exhibit rectification, that is, depend on Vleft/right exponentially:
(21)goVleftright,P=2·exp⁡P·VleftrightRo,gcVleftright,P=0.25·exp⁡P·VleftrightRc,
where Vleft/right is a voltage across the left or right hemichannel, while Ro and Rc are rectification constants.The conductance of the left hemichannel, whennl Cxs are closed, can be described as follows:
(22)gleftnl=nlgcVleftnl,P+6-nlgoVleftnl,P.Similarly, the conductance of the right hemichannel, whennr Cxs are closed, is
(23)grightn=nrgcVrightn,P+6-nrgoVrightn,P.During gating, conductance of subgates ranges betweengo(Vleftright,P) and gc(Vleftright,P), and the total conductance of the GJ channel can be found using steady-state probabilities of Markov-chain model:
(24)g=∑iπigleftVleftnl·grightVrightnrgleftVleftnl+grightVrightnr,
where πi is a steady-state probability for nl Cxs in the left hemichannel and nr Cxs in the left hemichannel to be closed.Conductance of the GJ channel depends on the voltage; that is, the circuit is nonlinear. In order to calculate voltage across each Cx, we used an iterative procedure [7]. We assumed that the value of voltage is settled, if a difference between voltage values, calculated at two consecutive iterations, is less than 0.1 percent. Calculation showed that at least 5 iterations were needed to achieve the aforesaid precision.As one can see, the evaluation of functional transition rates of SAN model is not a trivial task in this case. SAN formalism allows estimating steady-state probabilities directly from SAN descriptor but not building and storing infinitesimal generator, for example, by using shuffle algorithm. However, there would be a necessity to evaluate functional transition rates during each iteration for evaluation of steady-state probabilities. Thus, it would require too much CPU time in case of GJ models. Moreover, the number of system states of GJ models presented in this paper is relatively small; therefore we use the different approach. We apply SAN formalism to specify the system behaviour and to create equivalent Markov chain model. The use of Kronecker algebra representation of global infinitesimal generator helps to get the insight of matrix structure and to apply numerical methods for evaluation of a steady-state solution.


## 3.3. Numerical Solution of Two-State CTMC Models of the GJ Channel Containing 12 Two-State Subgates

It follows from (16)-(17) that subdiagonal blocks in (14) are diagonal matrices. These properties allow using numerical methods for the calculation of steady-state probabilities and we consider three algorithms for steady-state solution in detail: banded Gaussian elimination, direct solution by recursion, and block Gauss-Seidel methods.


### 3.3.1. Banded Gaussian Elimination for Steady-State Solution of the CTMC Model of GJ Channel Containing 12 Two-State Subgates

A square matrixQ=qij is called banded if its entries are zero outside of the diagonally bordered band, which can be described by the following equation:
(25)qij=0,ifj<i-k1orj>i+k2.In (25), numbers k1 and k2 are called left and right half-bandwidths, respectively. The bandwidth of the matrix m is equal to (k1+k2+1). For example, a matrix with k1=k2=1 is tridiagonal matrix, that is, matrix with bandwidth 3.Complexity. If a matrix has bandwidth m, a more efficient implementation of Gaussian elimination exists than the standard one, which has a complexity of O(n3). The solution of the linear system with bandwidth m has an approximate complexity of O(m2n). To be exact, the complexity of banded Gaussian elimination is nm+12/4, while it is (4n3+9n2-13n)/6 for standard Gaussian elimination [24].From (14) it follows that Q has bandwidth m=15. Thus, it requires approximately 13 times less CPU time to apply banded Gaussian elimination to solve an equivalent DTMC model, which has a dense transition probability matrix.


### 3.3.2. Recursive Method for Steady-State Solution of CTMC Model of GJ Channel Containing 12 Two-State Subgates

An algorithm similar to the Thomas algorithm for tridiagonal matrices can be used to calculate steady-state probabilities of the GJ model. We use the matrix form of solution technique as presented in [14]. Infinitesimal generator Q can be divided into four blocks as follows:
(26)Vl=Q11Q210000T,X=0,Y=0000Q76Q77,W=Q1200000Q22Q230000Q32Q33Q340000Q43Q44Q450000Q54Q55Q560000Q65Q66Q67.Dividing vectorπ into segments, solution of
(27)π*π7VWXY=0
can be implemented by solving π7YW-1V=0 in two steps. At first, solving WZ=V for Z gives W-1V, while YZ gives coefficient matrix for solving π7. After that, the remaining part π* of steady-state vector π can be found from π*W=π7Y.Complexity. The procedure for obtaining a recursive solution can be implemented very efficiently due to the structure of the infinitesimal generator Q. For example, computation of Z is basically a backward substitution, since W is lower triangular. Also, finding the inverse of subdiagonal blocks is a trivial task, since these blocks are diagonal matrices.Since the size of state-spacen is not large for this Markov model, an approximate complexity evaluation by using big O notation might be too general in this case. Therefore, we evaluated the amount of operations necessary to implement the recursive procedure in more detailed way. We distinguished 6 types of distinct operations (e.g., matrix summation, matrix multiplication, etc.) adapted to different types of operands, such as dense matrix and tridiagonal matrix. A conservative estimation of number of arithmetic operations is presented in Table 1. We assume that these operations are implemented in the most basic way (e.g., we use cij=∑i=1naikbkj for matrix multiplication C=AB).Table 1
Evaluation of the number of arithmetic operations necessary to implement the recursive procedure for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Matrix + matrix
11
n
2
Matrix * matrix
6
n
3 − n2
Matrix * diagonal matrix
13
n
2
Vector * diagonal matrix
6
n
Vector * tridiagonal matrix
7
5
n
Solve dense system
1
(4n3 + 9n3 − 13n3)/6Detailed evaluation showed that recursive solution requires about 1.8 times less CPU time than banded Gaussian elimination and at least 23 times less than standard Gaussian elimination.Stability. The main problem of the block recursive procedure is numerical stability, due to rounding errors [14]. However, these problems are mitigated by the fact that matrix entries are relatively small (in the range of 0.001–0.01).We compared the solution provided by the recursive procedure with the solution calculated using a stable numerical method. Experimental data showed that steady-state probabilities obtained by the recursive procedure differ less than 10−12 from an exact solution for this particular GJ model.


### 3.3.3. Block Gauss-Seidel Method for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Two-State Subgates

The block Gauss-Seidel method is an iterative technique and thus eliminates stability concerns completely [14]. It can also be implemented very efficiently for block tridiagonal matrices.If solution vectorπ is divided according to the block structure of Q, then at k+1 outer iteration it is required to solve 7 inner iterations, which may be written as follows:
(28)π1k+1=-π2kQ21Q11-1;πik+1=-πi-1k+1Qi-1,1+πi+1kQi+1,1Q11-1,i=2,6¯;π7k+1=-π6k+1Q67Q77-1.Complexity. In this case, diagonal blocks are tridiagonal matrices and the linear system solution has a complexity of O(n). The number of operations (including a proof for convergence) necessary to perform a single outer iteration is presented in Table 2.Table 2
Number of arithmetic operations necessary to implement a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
5
n
Vector * tridiagonal matrix
12
5n
Solve tridiagonal system
7
8n
Check for convergence
1
nThe efficiency of the whole algorithm depends on convergence speed. That is, block Gauss-Seidel method would be more efficient than the recursive procedure if it required 4 or less iterations. Similarly, it would be more efficient than banded Gaussian elimination if the number of outer iterations was less than 7, and, finally, it would be more efficient than standard Gaussian elimination if block Gauss-Seidel required less than 96 outer iterations.We evaluated the number of outer iterations necessary to find a steady-state solution of the GJ model containing 12 two-state gates atVj=40 mV. Each time an initial iteration vector was chosen as a standard vector with equal entries, that is, each entry equal to 1/n. We assumed that necessary precision ε is achieved if the following condition was satisfied:
(29)max⁡iπik+1-πik<ε.Inequality (29) means that all entries of consecutive iterations differ less than ε in absolute value. The results of a convergence are presented in Table 3.Table 3
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Precision
Number of iterations
1
0
-
4
15
1
0
-
5
18
1
0
-
6
20
1
0
-
7
23
1
0
-
8
25
1
0
-
9
28
1
0
-
10
31
1
0
-
11
33
1
0
-
12
36
1
0
-
13
39
1
0
-
14
41
1
0
-
15
44Thus, for this particular GJ model the block Gauss-Seidel method is more efficient than standard Gaussian elimination at any precision level. However it is less efficient than the direct methods, for example, banded Gaussian algorithm or the recursive procedure presented in Section3.3.2.In addition, modification of the block Gauss-Seidel method outperformed other standard iterative algorithms (Jacobi, Gauss-Seidel) as well as projection methods (Arnoldi, GMRES, and BiCGSTAB). While the convergence of the fastest of projection methods, BiCGSTAB, was slightly better than that of block Gauss-Seidel, overall CPU time was longer (about 18 percent), since it required more time to perform a single iteration.


### 3.3.4. Repetitive Model Solution

Moreover, since the block Gauss-Seidel method is an iterative technique, it can be implemented more efficiently for repetitive solutions, which are especially important in the search for optimal model parameters. Iterative methods have an advantage over direct methods, since the previous solution vector can be used as a starting point for the solution of model with different set of parameters.A solution of the model at differentVj values can be described using Pseudocode 1.Pseudocode 1
(1)Q(1) ←FormInfinitesimalGenerator(V1);
(2)it ←SetInitialIterationVector();
(3)π(1) ←SteadyStateSolution(Q(1), it);
(4)C1 ←EstimateGJConductance(π(1));
(5) fori = 2 to k do
Q(i) ←FormInfinitesimalGenerator(Vi);
π(i) ←SteadyStateSolution(Q(i), π(i-1));
C1 ←EstimateGJConductance(π(i));
end   for.A similar procedure can be applied not only at differentVjs, but also with other gating parameters as well.It is known [25] that the difference between steady-state solutions of two linear systems, Q·π=0 and Q+ΔQ·π+Δπ=0, is constrained by the following relationship between norms of matrices and vectors:
(30)Δππ≤Q#·ΔQ;Q# is group inverse of infinitesimal generator Q.Thus, steady-state vectorsπi are relatively close to each other if matrices Q and Q+ΔQ are close and Q# is not large.Simulation ofVj-gating partially satisfies aforementioned conditions, since changes of entries of Q are in the range of 0.0001–0.001 due to the voltage change from 40 mV to 41 mV, while the norm Q# is equal to 213.73 at 40 mV level.In order to evaluate an effect of iterative methods for the repetitive model solution, more detailed experimental research was performed. We changed voltage across GJ channel from 0 to 100 mV by 0.1 mV intervals. Thus, 1000 different infinitesimal generators were built and the steady-state solution was calculated according to a scheme presented in Pseudocode1. Firstly, we used standard iteration vector with equal entries each time (we will refer to it as “Method I”), while for the second round of calculation a previous steady-state solution was used each time, as presented in Pseudocode 1 (we will refer to it as “Method II”). We evaluated the number of outer iterations necessary to achieve 10−6 precision for both cases. The results are presented in Table 4.Table 4
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
15
6
40
20
10
60
26
16
80
19
11
100
11
5A positive effect of “Method II” is obvious. The number of outer iterations decreases from about 30 to 60 percent depending onVj level. Overall, it required about 38 percent less CPU time to perform calculations by using “Method II” instead of “Method I.” CPU time in this case was comparable to that of banded Gaussian elimination.


## 3.3.1. Banded Gaussian Elimination for Steady-State Solution of the CTMC Model of GJ Channel Containing 12 Two-State Subgates

A square matrixQ=qij is called banded if its entries are zero outside of the diagonally bordered band, which can be described by the following equation:
(25)qij=0,ifj<i-k1orj>i+k2.In (25), numbers k1 and k2 are called left and right half-bandwidths, respectively. The bandwidth of the matrix m is equal to (k1+k2+1). For example, a matrix with k1=k2=1 is tridiagonal matrix, that is, matrix with bandwidth 3.Complexity. If a matrix has bandwidth m, a more efficient implementation of Gaussian elimination exists than the standard one, which has a complexity of O(n3). The solution of the linear system with bandwidth m has an approximate complexity of O(m2n). To be exact, the complexity of banded Gaussian elimination is nm+12/4, while it is (4n3+9n2-13n)/6 for standard Gaussian elimination [24].From (14) it follows that Q has bandwidth m=15. Thus, it requires approximately 13 times less CPU time to apply banded Gaussian elimination to solve an equivalent DTMC model, which has a dense transition probability matrix.


## 3.3.2. Recursive Method for Steady-State Solution of CTMC Model of GJ Channel Containing 12 Two-State Subgates

An algorithm similar to the Thomas algorithm for tridiagonal matrices can be used to calculate steady-state probabilities of the GJ model. We use the matrix form of solution technique as presented in [14]. Infinitesimal generator Q can be divided into four blocks as follows:
(26)Vl=Q11Q210000T,X=0,Y=0000Q76Q77,W=Q1200000Q22Q230000Q32Q33Q340000Q43Q44Q450000Q54Q55Q560000Q65Q66Q67.Dividing vectorπ into segments, solution of
(27)π*π7VWXY=0
can be implemented by solving π7YW-1V=0 in two steps. At first, solving WZ=V for Z gives W-1V, while YZ gives coefficient matrix for solving π7. After that, the remaining part π* of steady-state vector π can be found from π*W=π7Y.Complexity. The procedure for obtaining a recursive solution can be implemented very efficiently due to the structure of the infinitesimal generator Q. For example, computation of Z is basically a backward substitution, since W is lower triangular. Also, finding the inverse of subdiagonal blocks is a trivial task, since these blocks are diagonal matrices.Since the size of state-spacen is not large for this Markov model, an approximate complexity evaluation by using big O notation might be too general in this case. Therefore, we evaluated the amount of operations necessary to implement the recursive procedure in more detailed way. We distinguished 6 types of distinct operations (e.g., matrix summation, matrix multiplication, etc.) adapted to different types of operands, such as dense matrix and tridiagonal matrix. A conservative estimation of number of arithmetic operations is presented in Table 1. We assume that these operations are implemented in the most basic way (e.g., we use cij=∑i=1naikbkj for matrix multiplication C=AB).Table 1
Evaluation of the number of arithmetic operations necessary to implement the recursive procedure for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Matrix + matrix
11
n
2
Matrix * matrix
6
n
3 − n2
Matrix * diagonal matrix
13
n
2
Vector * diagonal matrix
6
n
Vector * tridiagonal matrix
7
5
n
Solve dense system
1
(4n3 + 9n3 − 13n3)/6Detailed evaluation showed that recursive solution requires about 1.8 times less CPU time than banded Gaussian elimination and at least 23 times less than standard Gaussian elimination.Stability. The main problem of the block recursive procedure is numerical stability, due to rounding errors [14]. However, these problems are mitigated by the fact that matrix entries are relatively small (in the range of 0.001–0.01).We compared the solution provided by the recursive procedure with the solution calculated using a stable numerical method. Experimental data showed that steady-state probabilities obtained by the recursive procedure differ less than 10−12 from an exact solution for this particular GJ model.


## 3.3.3. Block Gauss-Seidel Method for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Two-State Subgates

The block Gauss-Seidel method is an iterative technique and thus eliminates stability concerns completely [14]. It can also be implemented very efficiently for block tridiagonal matrices.If solution vectorπ is divided according to the block structure of Q, then at k+1 outer iteration it is required to solve 7 inner iterations, which may be written as follows:
(28)π1k+1=-π2kQ21Q11-1;πik+1=-πi-1k+1Qi-1,1+πi+1kQi+1,1Q11-1,i=2,6¯;π7k+1=-π6k+1Q67Q77-1.Complexity. In this case, diagonal blocks are tridiagonal matrices and the linear system solution has a complexity of O(n). The number of operations (including a proof for convergence) necessary to perform a single outer iteration is presented in Table 2.Table 2
Number of arithmetic operations necessary to implement a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
5
n
Vector * tridiagonal matrix
12
5n
Solve tridiagonal system
7
8n
Check for convergence
1
nThe efficiency of the whole algorithm depends on convergence speed. That is, block Gauss-Seidel method would be more efficient than the recursive procedure if it required 4 or less iterations. Similarly, it would be more efficient than banded Gaussian elimination if the number of outer iterations was less than 7, and, finally, it would be more efficient than standard Gaussian elimination if block Gauss-Seidel required less than 96 outer iterations.We evaluated the number of outer iterations necessary to find a steady-state solution of the GJ model containing 12 two-state gates atVj=40 mV. Each time an initial iteration vector was chosen as a standard vector with equal entries, that is, each entry equal to 1/n. We assumed that necessary precision ε is achieved if the following condition was satisfied:
(29)max⁡iπik+1-πik<ε.Inequality (29) means that all entries of consecutive iterations differ less than ε in absolute value. The results of a convergence are presented in Table 3.Table 3
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Precision
Number of iterations
1
0
-
4
15
1
0
-
5
18
1
0
-
6
20
1
0
-
7
23
1
0
-
8
25
1
0
-
9
28
1
0
-
10
31
1
0
-
11
33
1
0
-
12
36
1
0
-
13
39
1
0
-
14
41
1
0
-
15
44Thus, for this particular GJ model the block Gauss-Seidel method is more efficient than standard Gaussian elimination at any precision level. However it is less efficient than the direct methods, for example, banded Gaussian algorithm or the recursive procedure presented in Section3.3.2.In addition, modification of the block Gauss-Seidel method outperformed other standard iterative algorithms (Jacobi, Gauss-Seidel) as well as projection methods (Arnoldi, GMRES, and BiCGSTAB). While the convergence of the fastest of projection methods, BiCGSTAB, was slightly better than that of block Gauss-Seidel, overall CPU time was longer (about 18 percent), since it required more time to perform a single iteration.


## 3.3.4. Repetitive Model Solution

Moreover, since the block Gauss-Seidel method is an iterative technique, it can be implemented more efficiently for repetitive solutions, which are especially important in the search for optimal model parameters. Iterative methods have an advantage over direct methods, since the previous solution vector can be used as a starting point for the solution of model with different set of parameters.A solution of the model at differentVj values can be described using Pseudocode 1.Pseudocode 1
(1)Q(1) ←FormInfinitesimalGenerator(V1);
(2)it ←SetInitialIterationVector();
(3)π(1) ←SteadyStateSolution(Q(1), it);
(4)C1 ←EstimateGJConductance(π(1));
(5) fori = 2 to k do
Q(i) ←FormInfinitesimalGenerator(Vi);
π(i) ←SteadyStateSolution(Q(i), π(i-1));
C1 ←EstimateGJConductance(π(i));
end   for.A similar procedure can be applied not only at differentVjs, but also with other gating parameters as well.It is known [25] that the difference between steady-state solutions of two linear systems, Q·π=0 and Q+ΔQ·π+Δπ=0, is constrained by the following relationship between norms of matrices and vectors:
(30)Δππ≤Q#·ΔQ;Q# is group inverse of infinitesimal generator Q.Thus, steady-state vectorsπi are relatively close to each other if matrices Q and Q+ΔQ are close and Q# is not large.Simulation ofVj-gating partially satisfies aforementioned conditions, since changes of entries of Q are in the range of 0.0001–0.001 due to the voltage change from 40 mV to 41 mV, while the norm Q# is equal to 213.73 at 40 mV level.In order to evaluate an effect of iterative methods for the repetitive model solution, more detailed experimental research was performed. We changed voltage across GJ channel from 0 to 100 mV by 0.1 mV intervals. Thus, 1000 different infinitesimal generators were built and the steady-state solution was calculated according to a scheme presented in Pseudocode1. Firstly, we used standard iteration vector with equal entries each time (we will refer to it as “Method I”), while for the second round of calculation a previous steady-state solution was used each time, as presented in Pseudocode 1 (we will refer to it as “Method II”). We evaluated the number of outer iterations necessary to achieve 10−6 precision for both cases. The results are presented in Table 4.Table 4
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 12 two-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
15
6
40
20
10
60
26
16
80
19
11
100
11
5A positive effect of “Method II” is obvious. The number of outer iterations decreases from about 30 to 60 percent depending onVj level. Overall, it required about 38 percent less CPU time to perform calculations by using “Method II” instead of “Method I.” CPU time in this case was comparable to that of banded Gaussian elimination.


## 3.4. CTMC Model of the GJ Channel Containing 6 Three-State Gates

We assume that in this GJ model only subgates in the left hemichannel operate [4], while subgates in the right hemichannel are always open (see Figure 3).Figure 3
Electrical scheme of the GJ channel composed of two hemichannels each formed of 6 connexins/subgates.Vj influence both hemichannels but only Cxs on the left operate between open, closed, and deep closed states, while Cxs on the right are always open.We also assume that each subgate operates between open (o), closed (c), and deep-closed (d) states. The transition among these states is presented in Figure 4.Figure 4
Three-state transition graph of a subgate.In this case our SAN model consists of a single automatonA3l (subscript value 3 denotes that each subgate has 3 possible states), which describes the left hemichannel. If we assume that states of the left hemichannel are numbers of open and closed gates, denoted by no and nc, respectively, then the state-space of a system consists of 2-tuples (no,nc) satisfying the following inequality:
(31)no+nc≤6.It follows from (31) that the state-space has the size of 28. From a state no,nc automaton can go to the state no+1,nc-1 with transition rate nc·λco; to the state no-1,nc+1 with transition rate no·λoc; to the state no,nc+1 with transition rate 6-no-nc·λdc; and finally to the state no,nc-1 with transition rate nc·λcd.An infinitesimal generatorQ3l of the left hemichannel (as well as the global system generator, i.e., Q3l=Q36) has the same block tridiagonal structure as in (14):
(32)Q36=Q11Q1200000Q21Q22Q2300000Q32Q33Q3400000Q43Q44Q4500000Q54Q55Q5600000Q65Q66Q7600000Q76Q77.However, all the blocks in (32) including zero-entry blocks are of varying sizes. In general, block entry ij of the infinitesimal generator is of size 8-i×8-j. For example, diagonal blocks Qii are square matrices of size 8-i each and have the following tridiagonal form:
(33)Qii=*7-iλdc⋮00λcd*⋮0002λcd⋮00⋯⋯⋱⋯⋯00⋮2λdc000⋮*λdc00⋮7-iλcd*,
where λdc=λdc(Vleftno,nc)=λdc(Vlefti,j) and λcd=λcd(Vleftno,nc)=λcd(Vlefti,j) and j is the row in a block Qii where λdc or λcd appears.All upper diagonal blocksQi,i+1 have the following structure (zero-entries row vector augmented with diagonal matrix):
(34)Qi,i+1=00⋮0λco0⋮002λco⋯0⋮⋮⋮000⋮7-iλco,
where λco=λco(Vleftno,nc)=λco(Vlefti-1,j-1) and j is the row in a block Qi,i+1 where λco appears.Similarly, lower diagonal blocksQi+1,i are diagonal matrices augmented with a zero-entry column and may be written as follows:
(35)Qi+1,i=0i-1λoc0⋮000i-1λoc⋮0⋯⋯⋯⋱⋯000⋮i-1λoc,
where λoc=λoc(Vleftno,nc)=λoc(Vlefti-1,j-1) and j is the row in a block Qi+1,i, where λco appears.The first problem arising in steady-state calculation is that the blocks are of different sizes. It means that the recursive procedure, which was most efficient for GJ models with 12 two-state Cxs, cannot be applied in this case. This leaves only banded Gaussian elimination and block Gauss-Seidel methods for further detailed consideration.


### 3.4.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Subgates

It is easy to see from (32) that Q36 has the same bandwidth m=15 as Q212 but the size of state-space n=28 is different, in this case. So, according to the complexity evaluation presented in [24], the steady-state solution by using banded Gaussian elimination requires only about 4-fold less CPU time than standard Gaussian elimination for dense linear system. Thus, the difference is not as pronounced as in the previous example.


### 3.4.2. Block Gauss-Seidel Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Gates

The application of block Gauss-Seidel is very similar to that for GJ model with 12 two-state Cxs. Basically, the same iterative procedure (28) can be applied; however blocks are of different sizes in this case. Thus, even though the same basic operations with the same complexity as presented in Table 2 are used for this model, one must evaluate varying sizes of blocks in the matrix Q36. For example, instead of solving 7 tridiagonal systems, each of size 7, one needs only to solve one system of size 7, one of size 6, and so forth.This gives an estimated complexity of 196 per single outer iteration with the block Gauss-Seidel method. Thus, block Gauss-Seidel outperforms standard Gaussian elimination if less than 80 outer iterations are needed. It also outperforms banded Gaussian elimination if less than 18 outer iterations are needed.As for the 12 two-state Cxs GJ model, we evaluated the number of outer iterations necessary to achieve required precision. The convergence speed is presented in Table5.Table 5
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
20
1
0
-
6
25
1
0
-
7
30
1
0
-
8
35
1
0
-
9
40
1
0
-
10
45
1
0
-
11
50
1
0
-
12
56
1
0
-
13
61
1
0
-
14
66
1
0
-
15
71Thus, it is less feasible to use block Gauss-Seidel method than banded Gaussian elimination if higher than 10−5 precision is used, though it is more efficient than standard Gaussian elimination even with 10−15 precision.However, the efficiency of block Gauss-Seidel becomes higher if the repetitive model solution is performed. A similar experiment as with the 12 two-state Cxs model was performed for 6 three-state subgates GJ model. The results are presented in Table6.Table 6
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
12
7
40
18
15
60
20
9
80
14
4
100
12
3The results showed that block Gauss-Seidel becomes more efficient than banded Gaussian elimination under reasonable 10−6 precision if repetitive calculations are performed.


## 3.4.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Subgates

It is easy to see from (32) that Q36 has the same bandwidth m=15 as Q212 but the size of state-space n=28 is different, in this case. So, according to the complexity evaluation presented in [24], the steady-state solution by using banded Gaussian elimination requires only about 4-fold less CPU time than standard Gaussian elimination for dense linear system. Thus, the difference is not as pronounced as in the previous example.


## 3.4.2. Block Gauss-Seidel Elimination for Steady-State Solution of CTMC Model of GJ Channel Containing 6 Three-State Gates

The application of block Gauss-Seidel is very similar to that for GJ model with 12 two-state Cxs. Basically, the same iterative procedure (28) can be applied; however blocks are of different sizes in this case. Thus, even though the same basic operations with the same complexity as presented in Table 2 are used for this model, one must evaluate varying sizes of blocks in the matrix Q36. For example, instead of solving 7 tridiagonal systems, each of size 7, one needs only to solve one system of size 7, one of size 6, and so forth.This gives an estimated complexity of 196 per single outer iteration with the block Gauss-Seidel method. Thus, block Gauss-Seidel outperforms standard Gaussian elimination if less than 80 outer iterations are needed. It also outperforms banded Gaussian elimination if less than 18 outer iterations are needed.As for the 12 two-state Cxs GJ model, we evaluated the number of outer iterations necessary to achieve required precision. The convergence speed is presented in Table5.Table 5
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
20
1
0
-
6
25
1
0
-
7
30
1
0
-
8
35
1
0
-
9
40
1
0
-
10
45
1
0
-
11
50
1
0
-
12
56
1
0
-
13
61
1
0
-
14
66
1
0
-
15
71Thus, it is less feasible to use block Gauss-Seidel method than banded Gaussian elimination if higher than 10−5 precision is used, though it is more efficient than standard Gaussian elimination even with 10−15 precision.However, the efficiency of block Gauss-Seidel becomes higher if the repetitive model solution is performed. A similar experiment as with the 12 two-state Cxs model was performed for 6 three-state subgates GJ model. The results are presented in Table6.Table 6
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
12
7
40
18
15
60
20
9
80
14
4
100
12
3The results showed that block Gauss-Seidel becomes more efficient than banded Gaussian elimination under reasonable 10−6 precision if repetitive calculations are performed.


## 3.5. CTMC Model of the GJ Channel Containing 12 Three-State Subgates

Here, we consider that in the model each subgate of both hemichannels operates between open (o), closed (c), and deep closed (d) states. Thus, its electrical scheme is the same as presented in Figure 1, while the state graph of the subgate is as presented in Figure 3.We model this type of GJ by SAN, containing two automata. We assume thatA3l describes the left hemichannel, while A3r describes the right one (again, subscript values 3 denote the fact that each subgate has 3 possible states). The states of both automata A3l and A3r are 2-tuples nol,ncl and nor,ncr, respectively. Here nol and ncl denote the number of open and closed subgates on the left hemichannel, while nor and ncr denote the number of closed and open gates on the right one. They also must satisfy the following inequalities:
(36)nol+ncl≤6,nor+ncr≤6.Transitions among states in each hemichannel are analogous to those of the previous model. Similarly, infinitesimal generatorsQ3l and Q3r can be written as in (32). Thus global infinitesimal generator Q312 may be expressed as
(37)Q312=Q3l⊗gI28+I28⊗gQ3r.It is easy to see from (37) that Q312 has the size of 748; thus it is a much larger model than in previous examples. It is not possible due to the size of the matrix to present its full block structure. However, its nonzero entry structure, which was obtained by usingspy() function from MATLAB package, is presented in Figure 5.Figure 5
Nonzero entry structure of global system generatorQ312 of GJ channel composed of two hemichannels formed of 6 connexins with 3 states.It is also possible to analyze its structure based on the Kronecker representation of system descriptor (37). As can be seen from Figure 5, it consists of 5 layers of blocks, all of which are square matrices of size 28. Diagonal blocks Qii are all block tridiagonal matrices, which may be written as follows:
(38)Qii=qii⊗I7+Q36.
Here qii denotes the ith diagonal entry of the matrix Q36.It follows from (38) that Qii has the same nonzero entries structure as Q36. Matrix Q312 also has two layers of blocks in lower and upper parts. For simplicity, we call them inside-lower (inside-upper) and outside-lower (outside-upper) layers. All of these blocks are diagonal matrices and can be written as
(39)Qij=qij⊗I28,
where qij denotes the ijth entry of matrix Q36.Since matrixQ312 is not tridiagonal, it leaves banded Gaussian elimination and block Gauss-Seidel methods for more detailed consideration.


### 3.5.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Even though matrix (38) is banded, its bandwidth 393 is much bigger in both absolute and relative (m exceeds half of the size of n) values than that of 12 two-state Cxs GJ model. It requires about 5 times less CPU time than standard Gaussian elimination to calculate steady-state probabilities.


### 3.5.2. Block Gauss-Seidel Algorithm for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Analyzing the zero-entries structure of (38) allows for adaptation of the block Gauss-Seidel algorithm for Q312 model. Basically, in one outer iteration step one needs to solve 28 inner iterations—each of them is a linear system of size 28:
(40)πik+1=bQii-1,i=1,28¯,
where row vector b might consist of up to four vectors of form πrk+1Ql,m or πrkQl,m. In general, the number of arithmetic operations necessary to perform one outer iteration of the block Gauss-Seidel algorithm for Q312model is presented in Table 7 (size n in this case is equal to 28).Table 7
Number of operations necessary to perform a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
56
n
Vector * diagonal matrix
84
n
Solve tridiagonal system
28
8
n
Check for convergence
1
nThus, the block Gauss-Seidel algorithm becomes more efficient than standard Gaussian elimination if it requires less than 5954 outer iterations. Actual numbers of outer iterations necessary to achieve the required precision at 40 mV transjunctional voltage level are presented in Table8.Table 8
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
23
1
0
-
6
32
1
0
-
7
40
1
0
-
8
49
1
0
-
9
58
1
0
-
10
66
1
0
-
11
75
1
0
-
12
83
1
0
-
13
92
1
0
-
14
101
1
0
-
15
109Basically the convergence speed of block Gauss-Seidel for solving steady-state probabilities of the 12 three-state subgates GJ model is comparable to that of previous models. Also, block Gauss-Seidel is much more efficient than even banded Gaussian elimination with any precision. As in previous cases, it outperformed other standard iterative and projection methods.For example, it required less than 40 milliseconds of CPU time to calculate steady-state probabilities with 10−6 precision with MATLAB while its implementation in C++ required about 18 milliseconds.The repetitive model solution showed the same effect of iterative algorithms on convergence speed as in previous examples. The results are presented in Table9.Table 9
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
24
15
40
32
25
60
30
23
80
18
8
100
12
3Overall, about 40 percent less CPU time was required to estimate steady-state probabilities in the whole range of transjunctional voltage by using, if previous solutions were used as the first iteration vector.


## 3.5.1. Banded Gaussian Elimination for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Even though matrix (38) is banded, its bandwidth 393 is much bigger in both absolute and relative (m exceeds half of the size of n) values than that of 12 two-state Cxs GJ model. It requires about 5 times less CPU time than standard Gaussian elimination to calculate steady-state probabilities.


## 3.5.2. Block Gauss-Seidel Algorithm for Steady-State Solution of CTMC Model of GJ Channels Containing 12 Three-State Subgates

Analyzing the zero-entries structure of (38) allows for adaptation of the block Gauss-Seidel algorithm for Q312 model. Basically, in one outer iteration step one needs to solve 28 inner iterations—each of them is a linear system of size 28:
(40)πik+1=bQii-1,i=1,28¯,
where row vector b might consist of up to four vectors of form πrk+1Ql,m or πrkQl,m. In general, the number of arithmetic operations necessary to perform one outer iteration of the block Gauss-Seidel algorithm for Q312model is presented in Table 7 (size n in this case is equal to 28).Table 7
Number of operations necessary to perform a single outer iteration of block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Part of an algorithm
Number of times
Number of arithmetic operations
Vector + vector
56
n
Vector * diagonal matrix
84
n
Solve tridiagonal system
28
8
n
Check for convergence
1
nThus, the block Gauss-Seidel algorithm becomes more efficient than standard Gaussian elimination if it requires less than 5954 outer iterations. Actual numbers of outer iterations necessary to achieve the required precision at 40 mV transjunctional voltage level are presented in Table8.Table 8
Number of outer iterations necessary to achieve the required precision by using block Gauss-Seidel algorithm for GJ model with 12 three-state subgates.
Precision
Number of iterations
1
0
-
4
14
1
0
-
5
23
1
0
-
6
32
1
0
-
7
40
1
0
-
8
49
1
0
-
9
58
1
0
-
10
66
1
0
-
11
75
1
0
-
12
83
1
0
-
13
92
1
0
-
14
101
1
0
-
15
109Basically the convergence speed of block Gauss-Seidel for solving steady-state probabilities of the 12 three-state subgates GJ model is comparable to that of previous models. Also, block Gauss-Seidel is much more efficient than even banded Gaussian elimination with any precision. As in previous cases, it outperformed other standard iterative and projection methods.For example, it required less than 40 milliseconds of CPU time to calculate steady-state probabilities with 10−6 precision with MATLAB while its implementation in C++ required about 18 milliseconds.The repetitive model solution showed the same effect of iterative algorithms on convergence speed as in previous examples. The results are presented in Table9.Table 9
Number of outer iterations for repetitive model solution by using block Gauss-Seidel algorithm for GJ model with 6 three-state subgates.
Voltage, mV
Number of iterations
Method I
Method II
2
0
24
15
40
32
25
60
30
23
80
18
8
100
12
3Overall, about 40 percent less CPU time was required to estimate steady-state probabilities in the whole range of transjunctional voltage by using, if previous solutions were used as the first iteration vector.


## 4. Conclusion

SAN formalism is efficient for the creation of models of GJ voltage gating, because system description is relatively simple, and the building and storing of the infinitesimal generator is very rapid. We used SAN to create equivalent CTMC model due to the complexity of estimation of functional transition rates. Unlike a PLA approach, which we have used earlier for CTMC modelling of GJs [8], SAN and Kronecker algebra operations help to get more insight into the structure of infinitesimal generator matrix.Infinitesimal generators of GJ models have a distinct block structure that allows selecting most efficient numerical methods. For example, application of banded Gaussian method lowers CPU time at least 4-fold as compared to standard Gaussian elimination, which typically is applied for estimation of steady-state probabilities of DTMC models with dense matrices.Iterative methods are very suitable for GO of gating parameters, since it requires numerous simulations at differentVjs. In particular, the block Gauss-Seidel method can be applied very successfully, since it also benefits from the block structure of the infinitesimal generator. The implementations proposed in this study outperformed even direct methods used in calculation of steady-state probabilities.We assume that implementation of different numerical methods, for example, using the most advanced numerical techniques in SAN modelling, could lead to even better results. This could help to reduce computational time in search of most adequate mathematical models in describing voltage gating of GJs.



---

*Source: 936295-2015-02-01.xml*