INTRODUCTION
Throughout the world very little information is known regarding the sleep disorder
especially apnea. The work on data recording need much effort as the patient
need to go through a polysomnography test. During the polysomnography test,
the apnea events and sleep stages is recorded. Apnea is a paused in breathing
during sleep. Apnea may be characterized as Obstructive Sleep Apnea (OSA), Central
Apnea (CA), Mixed Apnea (MA) and hypopnea. Hypopnea is a partial apnea. Apnea
usually last for at least 10 sec and paused in breathing that less than 10 sec
is not characterized as apnea (Guilleminault et al.,
2001). Most of the studies used OSA as it is the frequent events during
sleep among apnea patients. In many parts of the world it is partly assumed
that apnea is a risk of automobile accident (Barbe et
al., 1999; TeránSantos et al., 1999).
This is because patients with OSA has difficulty to remain focus and give full
attention during driving automobiles.
Meanwhile, OSA is found to be associated with hypertension and cardiovascular
disease (Strohl, 1996). Moreover, studies have shown
that patients with OSA have lower score of quality of life based on the Health
Related Quality of Life (HRQOL) questionaire. Stepnowsky
et al. (2000) reported that HRQOL at lower level especially in those
with mild apnea compared to those with moderate to severe apnea. The identification
of mild, moderate and severe apnea has been discussed in many studies using
the ApneaHypopnea Index (AHI). The AHI is the total of apnea and hypopnea divided
with number of hour of sleep (Young et al., 1999). Lindberg
et al. (1999) for example has reported that AHI, increased from mild
to moderate apnea, during the ten years period of the followup study among
patients that is not treated. The classification is AHI>5 as mild, AHI(530)
as moderate and AHI>30 as severe. Moreover, OSA is more serious in older
age group (>65 years old) compared to younger age group (<25 years old)
and among men compared to women based on AHI.
During sleep there are four sleep stages which is wake, light sleep, deep sleep
and Rapid Eye Movement (REM). The sleep stage was recorded for every 30 sec
or epoch during sleep. Goh et al. (2000) found
that time of sleep in each sleep stages is varies. He found that AHI is higher
during REM compared to other sleep stages among children. Other study by O’Connor
et al. (2000) in United States showed that occurrence of apnea is
more frequent during REM sleep stages especially among women compared to men.
However, study by Ware et al. (2000) showed that
there was no significant difference, the frequency of apnea during REM and other
sleep stages between men and women. Therefore, other study have suggested that
apnea is more likely influence by cardiovascular disease, body mass index, smoking
habits (Lindberg et al., 1999; Shahar
et al., 2001).
Most studies of the characteristics of sleep mentioned above have described
simply summary of the sleep and wake cycle, with perhaps the subsequent assumption
that the characteristics of sleep is dependent on the previous sleep (Zung
et al., 1965; Yang and Hursch, 1973). This
type of analysis is discussed by Kemp (1986) using a
sleep data. Earlier study by Saat and Jemain (2009)
have shown that the most suitable distribution to represent hypopnea which is
the partial apnea is the Gamma distributions and Weibull distributions. However,
based on study by Saat et al. (2008) at least
500 observations is required in order to discriminate between both distribution.
There was very few study on sleep apnea and effects according to different sleep
stages and period of sleep. Therefore, study on sleep disorder especially apnea
and the effects on different sleep stages is essential in order to understand
the behavior of sleep apnea among adults. In this study, Markov chain model
will be used to determine whether the present of apnea is depending on the previous
event of apnea. Earlier study by Uysal and Ulus (2007)
used Markov chain model to model the threshold of algorithm for a database system.
MATERIALS AND METHODS
We analyze a database comprising 14 subjects with apnea problem. The data was
extracted from MITBIH database which is http://www.physionet.org/physiobank/database/
which is in 1999 (Ichimaru and Moody, 1999; Goldberger
et al., 2000). The data comprises of apnea event for every 30 sec
or for every epochs. One epoch is equivalent to 30 sec. There are three sleep
stages that is included in this study which is light sleep, deep sleep and REM.
Sleep stages were evaluated via the computer program based on the Rechtschaffen
and Kales (1968) methods. Stage 1 is drowsiness where people drift in and
out of sleep for about 5 to 10 min and can be awakened easily. Stage 2 is light
sleep where the eye movements stop. The heart rate slows and body temperature
decreases. Stage 3 and 4 is deep sleep and during this stage, there is no eye
movement or muscle activity. Rapid Eye Movement (REM), during this stage the
breathing becomes more rapid and people usually dream during this stage.
Markov chains models: Let, X_{1},X_{2},...,X_{nn}
be n binary variables which represent a sequence of the occurrence of apnea
and normal events, for a particular individual during the duration of sleep
for the length of period of n epochs, indicated as 1 and 0, respectively.
X_{t} = 0, noapnea
= 1, apnea

and t = 1,2,3,..,n epoch when the events were recorded. Consider that the period
of sleep for a particular individual can be divided into many epochs each of
length 30 sec (epoch). Since, the occurrence of an event in a particular epoch
is dependent on the event which has occurred in the earlier epoch it is suitable
to explain the sequence of event using a Markov chain model. The sequence of
apnea and normal breathing is assumed to follow a first order Markov Chain (MC)
model at time t, when at the time t, X_{t} depends on previous event
X_{t1}. The occurrence of apnea in a particular epoch is dependent
on the previous epoch.
For the first order of Markov chain, the stationary transition probabilities
is given by:
p_{hi} = P(X_{t} = iX_{t1}
= h)h, i = 0,1 
The conditional transition probabilities for the first order Markov chain at
time t is given by:
P_{00} = P(X_{t} = 0X_{t1} = 0)
P_{01} = P(X_{t} = 0X_{t1} = 1)
P_{11} = P(X_{t} = 0X_{t1} = 1)
P_{10} = P(X_{t} = 0X_{t1} = 0)

The estimation of the transition probabilities is given by:
Similarly, for the higher order of Markov chain the transition probabilities
can be written as:
Second order Markov chain:
p_{hij} = P((X_{t} = jX_{t1}
= i, X_{t2 }= h) h, i, j = 0,1 
For the third order of Markov chain:
p_{ghij }= P(X_{t} = jX_{t1}
= i, X_{t2} = h, X_{t3} = g) g, h, i, j = 0,1 
The estimation of the transition probabilities of the second and third order of Markov chain is given by:
Optimum order of Markov chain models: In determining the optimum order
of Markov chain models, two type of information criteria which is (Akaike's
Information Criteria) AIC and Bayesian Information Criteria (BIC) or loss function
was used. Both AIC and BIC is calculated by generating the loglikelihood function
for the estimated transition probabilities.
The loglikelihood is given by:
In this study, we are interested to determine the appropriate order of MC among
the set of competing order. Specifically we want to compare between mth and
(m1)th order model. The comparison of the two different MC models to decide
on the optimum order say MC models of order kth and rth order where, k<r
and k = 0,1,..., r1, is to form the log likelihood ratio, logθ_{k,r}.
The maximized likelihood ratio statistic is 2 logθ_{k,r}.
Where:
The loss function is denoted by AIC(k) (Chin, 1977),
which is given by:
where, v is the degree of freedom with A as the number of states. For this study A = 2 which represent two event which is apnea and normal breathing. Another loss function is based on BIC(k) which can be written as:
where, n is the sample size. The aim is to find the value of AIC and BIC the minimize the loss function.
Besson's coefficient persistence (R_{a}): Following the Brookes
and Carruthers (1953) the statistical test to examine the persistence of
the occurrence of apnea in sequences is Besson's coefficient of persistence
(R_{a}). It was defined as follows:
where, P_{a} is the probability of the apnea occurrence and P_{aa} is the conditional probability of the occurrence of apnea given the previous events was apnea.
Fitting Markov chain models: A sequence of apnea events is defined as a period of consecutive epoch say n apnea (no apnea) immediately preceded and followed by apnea (no apnea). In order to compute the frequency distribution of the sequence of apnea using Markov models, the following conditional probabilities will be obtained for the first, second, third and fourth order of Markov chain models. Similar approach is applied for the distribution of the no apnea events. The following notation will be used.
For the first order of Markov chain model the probability of the n apnea is given by:
For the second order of Markov chain model the probability of the one epoch
of apnea is given by:
p(010) = p_{0}p_{01}p_{010}

and the probability for more than one apnea following an apnea for the second order of Markov model is given by:
For the third order Markov chain model the probability of one and two epoch
that has occurrence of apnea is given by:
p(010) = p_{0}p_{01}p_{010
p(010) = p0p01p011p110 }

and the probability for more than two epoch that has occurrence of apnea for
the third order Markov chain model is given by:
For the fourth order Markov chain model the probability of one and two epoch
that has occurrence of apnea is given by:
p(010) = p_{0}p_{01}p_{010
p(0110) = p0p01p011p110
p(01110) = p0p01p011p0111p1110
} 
and the probability for more than two epoch that has occurrence of apnea for
the third order Markov chain model is given by:
The Chisquare goodness of fit test will be used to test for the appropriate
order of Markov chain models (Mendenhall et al., 1999).
The test is comparing the observed and the expected distributions of the apnea
(no apnea) using the first until fourth order of Markov chain models. The lowest
value of Chisquare indicating the most appropriate model. This is because the
lowest value of Chisquare between the first, second, third and fourth order
is representing the best fit.
RESULTS AND DISCUSSION
Characteristics of the sequence of apnea (no apnea): The conditional
probabilities of a apnea (no apnea) event at each 30 sec are estimated for different
sleep stages and first, second, third and fourth quarter of sleep . In Table
1, it is found that the conditional probability of an apnea given the previous
30 sec was apnea, P_{aa}, is substantially higher than the probability
of apnea, P_{a}, for all subjects. Furthermore, the difference between
the successive conditional probabilities of apnea reduces dramatically and becomes
negligible after about 2 or 3 epoch; however, this difference reduces after
about 4 or 5 epoch for subject 5,12 and 13.
Similarly, the conditional probabilities of no apnea events show that the probability P_{nn} is substantially higher than P_{n}. The difference between the successive conditional probabilities of no apnea reduces progressively and becomes negligible after about 5 epochs and about 2 or 3 epoch for subjects for 1 and 2 h, respectively. As expected, the analysis of apnea shows that the conditional probabilities of the apnea, P_{aa}, P_{aaa}, P_{aaaa} and P_{aaaaa} are lower than those of the no apnea P_{nn}, P_{nnn}, P_{nnnn} and P_{nnnnn} during sleep for all subjects.
This may be due to the fact that the apnea seldom lasts for more than five consecutive epoch in most subjects. Thus, it is evident to consider the fifth order Markov (r = 5) as the maximum order of the Markov process. Further analysis of the persistency of the apnea (no apnea) events will be explored by applying Besson’s Coefficient of Persistence (BCP). The result indicated that the BCP for subjects 5 is the highest (1.66) when compared to other subjects. However, subject 6 shows the lowest value of BCP (0.01).
The optimum order of Markov chain models: In determining the optimum order of the Markov chain models for a 5epoch sequence in the during sleep, the minimum loss function obtained from the two decision criteria, namely; the AIC and BIC, will be applied. Table 2 shows that the loss function obtained decision criteria AIC and BIC, consistently shows that the third order is the optimum order regardless of sleep stages. Based on Table 2, negative value of the loss function due to the value of log likelihood is more compared to the penalty. The minimum value of AIC and BIC is used in order to determine the optimum order of the Markov model (2v).
Table 1:  Persistency
of occurrence of apnea regardless of sleep stages and time of sleep 

Table 2:  The
loss function BIC(r) for various order of Markov chain, r, m = 4 

Bold
values indicate the minimum 
Table 3:  Optimum
order of Markov chain for apnea event according to AIC and BIC according
to sleep stages 

As an example, Table 3 shows that the loss function obtained
from the AIC and BIC (Eq. 2, 3) consistently
shows that the second order is found optimum in almost all the subjects for
light sleep stages using BIC. However, for the deep and REM sleep stages the
optimum order is less than two based on the BIC the optimum order for the apnea
events is found to be slightly lower than the optimum order obtained from AIC.
It is also shown that the optimum order estimated by the AIC is either greater
or equals to the BIC for most subjects during light sleep and deep sleep.
For the rest of the analysis, Table 4 displays the summary
of the optimum order of 5 epoch sequence of apnea and non apnea according to
first, second, third and fourth quarter duration of sleep and sleep stages.
It can be seen that the optimum order obtained from both, decision criteria
varies with sleep stages and hour of sleep. Generally, for both the AIC and
BIC and the sleep stages considered, the Markov chain of higher order is found
to be optimum for the 25% period of sleep for subject 6 and 11. However, for
the 50 and 75% period of sleep the optimum order higher than two is found to
the optimum order for subject 9 and 10.
Table 4:  Optimum
order of Markov chain for apnea event according to AIC and BIC for first,
second, third and fourth quarter period of sleep 

Table 5:  The
value of Chisquare goodness of fit test for various orders of Markov
chain models for the distribution of apnea events 

Bold
values indicate the minimum 
Moreover, for the fourth quarter period of sleep the optimum order is likely
less than three for most subjects. In addition for subject 1 the apnea event
is independent with the previous apnea event during all period of sleep. This
findings is supported by Katz (1981) indicated that
the optimum order based on the AIC was inconsistent and had a tendency to overestimate
the true optimum order, whereas the BIC produced more consistent results.
Table 4 shows that, in general it shows that the second order of Markov chain is the optimum order for describing the distributions of apnea during 25% period of sleep for most subjects except for subject 2,7 and 13 according to BIC. However, during the second, third and fourth period of sleep the optimum order is varies.
The most appropriate order of Markov chain models to explain the apnea (no
apnea) using various order of Markov chains is identified through the Chisquare
goodness of fit test. Table 5 provides the value of Chisquare
regardless of sleep staged and period of sleep, based on the most appropriate
order of the first four orders of the Markov chain models indicated as MC1,
MC2, MC3 and MC4 for the distributions of apnea and non apnea for the three
selected subjects, respectively. It is also found that a higher order of the
Markov chain models (order more than one) are observed to be more appropriate
in order to describe the distribution of apnea as shown in Table
5. Regardless of sleep stages, for the three sleep stages it is consistently
show that the higher order of Markov chain is found to be appropriate for representing
the distribution of apnea for most subjects.
CONCLUSIONS
The information of apnea behavior is important to the medical experts which can be used to make prediction of severity of apnea. The analysis of persistence of apnea (no apnea) add the information of the occurrence of apnea based on the previous epoch. The results based on analysis will provide a more information of the apnea occurrence during sleep. In this study, the Markov chain of various orders were applied on the apnea occurrences among patients in MITBIH hospital by considering the period of sleep and different sleep stages.
It can be concluded from this study that the 5 epoch of apnea occurrence varies
according to levels of hour of sleep and sleep stages . Generally, for all cases,
the results show that the optimum order identified by using AIC is higher compared
to BIC. The findings is supported by Jimoh and Webster (1986)
and Katz (1981) based on the simulation study that AIC
in inconsistent compared to BIC. Meanwhile, the order greater than one is optimum
order for most for all period of sleep. However, for the optimum order is higher
during light compared to deep and REM sleep stages. This study is supported
by study by Goh et al. (2000), who claimed that
the apnea is more frequent is second hour of sleep compared to first hour of
sleep. Their findings indicated that 55% of apnea occurs during REM sleep stages
and last period of sleep. They divide the hour of sleep into three periods.
Since, the higher order of Markov chain models is found to be optimum for the light sleep stages, indicating that the results may provide evidence that the higher the order of the chain, the greater the persistence of the apnea (no apnea) events especially for subject 9 and 10. Moreover, for the apnea event for the third order of Markov chain model is found to be the most appropriate order in most subjects regardless of sleep period and sleep stages.
Further analysis could be carried out by including other covariates so that many valuable information could be found and more prediction can be made to understand the behavior of apnea. In the future, it is suggested that the most appropriate probability models by comparing various orders of Markov model with the Bayesian model in representing the severity of apnea by considering the proportions of apnea events for each subject and other severity index such as ApneaHypopnea Index (AHI) and Respiratory Disturbance Index (RDI).
Generally the stationary pattern of apnea and non stationary pattern of apnea
are difference among subject between sleep stages. This may be due to the health
status of the subject. In addition (Bardwell et al.,
1999; Guillenimault et al., 2000) found that the occurrence of apnea
may be severe among subject that has depression, anger, anxiety and mood disturbance.
ACKNOWLEDGMENT
The authors like to express appreciation to Unit Penerbitan, Gugusan Kesihatan, Universiti Kebangsaan Malaysia for their financial support.