BACKGROUND
epigenetics studies the changes in gene function and gene expression that are not discernable by mutations in the dna sequence.
the area of biology devoted to epigenetics is a recent development and has a large amount of room for growth with new research on cancer, mammalian gene expression, and technological advances constantly being brought forth from the community.
epigenetic inheritance focuses on both mitotic and meiotic cellular changes and the processes involved.
looking at cell differentiation and genetic imprinting through epigenetics has created new leads for cancer research in terms of tumour growth.
the chromatin that controls dna processes is an epigenetic mechanism in either an active or repressive state.
there are three main mechanisms in epigenetics: dna methylation, histone modifications, and the binding of non-histone proteins  <cit> .
cpg islands  usually appear at the 5’ end of genes containing gc-rich dinucleotides.
normally, these regions are unmethylated; however, when methylation occurs, gene regulation is affected and methylation sometimes leads to carcinogenesis.
the importance of cgis has produced numerous algorithms throughout the community dedicated to locating and understanding these regions in dna  <cit> .
many of the traditional algorithms use the measures of length, gc content, and the number of observed over expected cpgs when determining if a section of dna is a cgi.
however, some newer algorithms employ a distance based detection method to identify cpg clusters  <cit> .
some of the features of unmethylated cpgs are their affinity to bind to a protein domain , their low mutation rate, and their association with open chromatin.
low methylation frequency has been correlated with high cpg density and vice versa.
dna methylation refers to the replacement of the attached hydrogen with a methyl group on a cytosine base, which causes the chromatin to become more compact affecting transcription factor binding  <cit> .
methylated cytosines will produce thymine when deaminated unlike unmethylated cytosines which produce uracil.
cpg density is lost due to the thymine mutation and this often inhibits the promoter regions of genes  <cit> .
the affect of methylation is particularly important in the case of cancer and the epigenetic modifications that silence tumour suppressor genes.
it has been observed that genes silenced epigenetically share sequence motifs in their promoter regions.
this is one of the possible ways to detect cancer hypermethylation  <cit> .
in genetics, a sequence motif is a short pattern of nucleotides that is deemed to have biological significance.
if a motif appears in the exonic region of a gene, it may encode the structural motif of a specific protein.
regulatory sequence motifs are located in areas where regulatory proteins such as transcription factors bind to the dna.
in order to find the most significant motifs in dna, many algorithms have been designed and applied to different organisms  <cit> .
when describing a motif, pattern notation using regular expressions is what depicts the sequence.
the de novo computational methods to discover important motifs take multiple input sequences and try to generate candidate motifs.
two of the most well-known algorithms often used by many researchers are blast and meme  <cit>  <cit> .
cpg islands are found in 40% of promoter and exonic regions of mammalian genes.
other areas of the genome contain very few cpg dinucleotides and these areas are normally methylated  <cit> .
methylation of promoter cpgs is known to cause gene silencing and is heavily implicated in carcinogenesis.
gardener-garden and frommer were the first researchers to use computational methods to detect and analyze cpg islands using specific criteria: 200-bp  length dna region, gc content greater than 50%, and observed cpg/expected cpg ratio  greater than  <dig>   <cit> .
although the original criteria provided a good starting point for cpg island detection, it didn’t take into account repeating regions of dna.
alu repeats are short interspersed elements repeating within the genome that are approximately 280-bp in length often containing a high gc content and obscpg/expcpg ratio  <cit> .
takai and jones analyzed human chromosomes  <dig> and  <dig> for cpg islands using their own algorithm that built upon the original criteria coined by gardener-garden and frommer.
the new algorithm reduced the number of detected cpg islands from  <dig>  to  <dig> , which is closer to the number of genes located on the two chromosomes .
using the same criteria, the new algorithm modifies the constraints of each criterion to produce better detection results.
now repeating elements such as alu are not considered as often as before .
the constraints for the new algorithm are as follows: length ≥ 500-bp, gc content ≥ 55%, and obscpg/expcpg ≥  <dig> .
cpgcluster  <cit>  discovers clusters of cpgs by looking at the distance between other cpgs on the same chromosome and applying statistical significance.
the two algorithms were compared using many different factors  to determine which is better at finding cgis  <cit> .
cpgcluster locates a much larger number of cgis; however, after further analysis only  <dig> % and  <dig> % mapped to promoter regions of the human and mouse genomes respectively.
the study found that often multiple clusters of cpgs from cpgcluster were substrings of one large cgi detected by the takai and jones algorithm.
since there is no length limitation when cpgcluster detects cgis, a much larger number of clusters are discovered.
gene expression is one of the most important functions in all forms of life.
transcription factors are encoded in about 3-5% of genes in eukaryotes allow the repression or activation of specific genes within dna.
chromatin plays another significant role in gene regulation and the network of interactions between transcription factors and chromatin structure is becoming increasingly important in epigenetic research.
dna methylation is an epigenetic memory mechanism involved in the silencing of genes within eukaryotic organisms.
histone modifications are another instrument in the epigenetic inheritance that passes information from parent to daughter cells.
post-translational modifications of core histone proteins have been linked to transcription repression and activation  <cit> .
aberrant methylation of promoter regions of genes has been linked to gene silencing and loss of expression in diseases like cancer  <cit>  and it is known that cancer mutation can cause alterations to protein signaling genes  <cit> .
single nucleotide polymorphisms  are the most common variation in the genetic sequence of the human genome.
studies continue to provide an increasing amount of evidence that snps are correlated with cancer and can be used as indicators of the disease  <cit> .
analyzing sequence variants in motifs within promoter regions of methylated genes could provide significant disease markers and possible sites for therapeutic study.
in this study, we examine several problems related to cpg islands and dna methylation of the promoter regions of genes:
• design a method of cgi detection using powerful algorithms that improves performance while incorporating the ability to correlate the methylation status of the dna with the location of the cgi.
• incorporate the power of analysis alongside cgi detection for an all-in-one program that covers the needs of the community.
• integrate motif finding into the detection algorithm, determine if the motifs are within cgis, and verify if they are within a transcriptional start site .
the rest of the paper is organized as follows.
we first present the conceptual framework on which the program was designed.
then the methodology of the finalized program is discussed.
finally, the first set of experiments is presented.
methods
the detection of cgis has evolved since the first detection algorithm was proposed by gardener-garden and frommer.
recently, studies have shown that incorporating the use of a hidden markov model in a detection algorithm can improve results  <cit> .
when establishing new techniques, it is still important to consider the traditional methods and integrate the best features of both into a new algorithm.
in our work, we combined a hidden markov model, the baum-welch algorithm, and the viterbi algorithm along with the traditional sliding window criteria to lower the detection of repeating elements.
hidden markov model
a hidden markov model  consists of a markov process in which the state is unobservable.
a markov process is a random phenomenon where future probabilities are determined based on the most recent values.
an hmm requires the knowledge of a few probabilities before it can be run on any data.
these probabilities are split into three separate groups:
• initial probabilities - the probabilities that determine which state the system will be in during the start of the algorithm.
often, the initial probabilities are equal among the different states  =  <dig> , p =  <dig> ).
• transition probabilities - the probabilities that provide the occurrence of a change from state i to state j  =  <dig> , p =  <dig> ).
• emission probabilities - the probabilities distinguishing each state based on the observations of the system  =  <dig> , p =  <dig> ).
estimating parameters
hmms have three distinct sets of parameters or probabilities: the initial state probabilities that determine which state the system starts in; the transition probabilities that decide if the state will switch after a certain period of time; and the emission probabilities showing whether the current symbol output belongs to one state or another.
for an hmm to decode a sequence into a path of states, the parameters need to be trained on a sequence of symbols to detect the final probabilities the system will use when finding the viterbi path.
one of the best and most efficient methods of estimating probabilities is through the use of the baum-welch algorithm, which is a special case of expectation-maximization.
the baum-welch algorithm is often used in hmms to estimate the unknown parameters or probabilities.
it is also known as the forward-backwards algorithm and is a special case of the generalized expectation-maximization algorithm.
it can produce maximum likelihood and posterior mode estimates for model parameters when given only the emission probabilities to work with.
the algorithm starts by assigning initial probabilities to all of the model parameters.
then it continues until convergence happens by adjusting the probabilities of each model parameter to increase the probability of the model in accordance with the training set being scanned.
viterbi algorithm
the viterbi algorithm uses dynamic programming to find the most likely sequence that the hidden states would take based on the observations in a parameterized model.
this sequence is called the viterbi path and it is usually related to hmms.
the viterbi algorithm is very similar to the forward algorithm which computes the probability that a set of observed events was generated by the model.
the algorithm was designed in  <dig> by andrew viterbi to decode convolutional codes within the noise of digital communication links.
the algorithm takes a hmm with possible q states, initial probabilities πi where i is the current state of the model, and transition probabilities ai,j where i, j is the change from state i to state j .
given a sequence of observable data x <dig> …,xl , the algorithm will generate a state sequence q <dig>  …,ql for each observable value.
the algorithm produces the final output using recurrence relations.
vl,k is the probability of the most likely state sequence based on the current l +  <dig> observations.
the state sequence can be recovered by saving in memory the state q is in during the run through the second equation.
then say there is a function, st that returns the value of q which produced vl,k when l >  <dig> and k when l =  <dig>  the viterbi path can be discovered using the following:
dna methylation analysis
once the cgi detection algorithm runs and scans the genetic sequence, the researcher can use the detected island locations to create primer sequences to determine the methylation status of the cgi.
often, a separate statistics program is used to calculate significance.
in our work, the analysis of the data is available using the p-value derived from the kolmogorov-smirnov two-sample test and the distribution of methylated to unmethylated islands is tabulated through the calculation of the z-score.
the kolmogorov-smirnov test uses minimum distance estimation to compare sample datasets with reference probability distributions equating them with a one-dimensional probability distribution.
the test can be performed with one sample dataset  or with two sample datasets .
the test either defines the mathematical distance between the empirical distribution function of a set of data and the cumulative distribution function of the reference distribution  or the distance between the empirical distribution of two separate sets of data .
the samples calculated under the null hypothesis are taken from the reference distribution  or the same distribution  and form the null distribution for the test.
when the kolmogorov-smirnov test is used as a goodness of fit test, the data is normalized and compared to a standard normal distribution.
the kolmogorov-smirnov statistic uses the empirical distribution function where  are a set of ordered data points,
where 1{yi ≤ x} is the indicator function.
the kolmogorov statistic for a cumulative distribution function e can be calculated using,
which calculates the supremum of the distances in the set, sup x. the kolmogorov-smirnov statistic often requires a large set of data to give an accurate acceptance or rejection of the null hypothesis; however, since we are working with the human genome and chromosomes seem to contain a large amount of cgis  <cit>  <cit>  and thus our datasets should be large enough to produce accurate p-values.
in our work, we use the two-sample k-s test to determine if two datasets  differ in their probability distributions in regards to length, gc content, and obs/exp ratio.
the two-sample k-s test uses the kolmogorov statistic
where  and  are the empirical distribution functions of each sample.
program architecture
there are a multitude of detection programs that use many different algorithms to accurately detect cgis within a genetic sequence.
some of the most popular cgi detection algorithms are gardener-garden and frommer  <cit> , cpg island searcher  <cit> , and cpgprod  <cit> .
the gardener-garden and frommer algorithm is the original cgi detection algorithm which uses a sliding window of  <dig> bp along with a gc content greater than 50% and an observed-to-expected cpg ratio greater than  <dig> .
the cpg island searcher built upon the original foundation using a window of  <dig> bp, gc content ≥ 55%, and obscpg/expcpg ≥  <dig> .
the cpgprod algorithm searches a genome for cgis using two steps:  search for all cgis in a submitted sequence based of the traditional criteria, and  predict the orientation of promoters once the start cgi is discovered  <cit> .
we decided to design a graphical user interface  for our cgi detection program to provide accessibility for researchers that are not well-versed in scripting or working with programs depending on the command prompt.
while both the cpg island searcher and cpgprod have a web server that provides a user interface, it is not feasible to run an dataset as large as a human chromosome through the web.
both programs must be run using typed commands and parameters if not running them through the web and do not provide the same interface as on the web for the user.
layout and design
the original cgi detection layout and code was released by tanner helland  under the bsd license.
it was originally written and designed in microsoft visual basic  <dig> , but we updated and modified the code using microsoft visual basic .net and microsoft visual studio  <dig>  the gui provides an intuitive method for loading the fasta sequence file, setting up the hmm parameters, estimating the parameters based on the file, and running the algorithm.
once the viterbi algorithm has defined when the sequence is in an island state  or a normal state , the sliding window can be run to detect where the islands are located within the genomic sequence which show inside the graphs for obscpg/expcpg ratio and i/b ratio.
once the sliding window has scanned for cgis, the results are shown in the textbox to the right .
we modified the layout to use a tab control in order to switch between the cgi detection and the analysis of the results.
the analysis tab contains a small spreadsheet for the detected islands where the user can change the methylation status  and can enter a methylation score for each island.
methylation scores have been used in many different studies  <cit>  <cit>  <cit>  as a measure of the strength of the methylation of a specific cgi to determine whether to classify it as methylated or unmethylated.
once the user has filled in the values for methylation status and score for each cgi, the analysis of the data can be completed.
the table next to the spreadsheet displays the separate mean values for cgi length, gc content, and obscpg/expcpg ratio for the unmethylated and methylated cgis.
the p-values are calculated using the kolmogorov-smirnov two-sample test.
the chart underneath the spreadsheet displays the z-score distribution for the methylated and unmethylated cgis determined by using the methylation scores entered by the user.
the final chart shows the distribution of lengths of the cgis across the two sets of data .
we created this layout and design to provide practicality for users that are not computational experts and to offer an all-in-one solution for detecting and analyzing cgi data.
RESULTS
methylation analysis
looking at the composition of cgis when methylated and unmethylated is important in the study of the epigenetic mechanism of methylation.
the list of promoters from weber et al.
<cit>  was evaluated by taking the promoters found within chromosome  <dig> and analyzing them using the cpg island detection  <dig>  program analysis tab.
the  <dig> promoters were selected based on the promoter class given to each in the previous work.
those with a class of hcp or icp were considered to contain cgis within or covering the promoter region when looking at methylation.
a cgi was considered methylated if the 5mc log <dig> ratio  <dig>  and unmethylated otherwise.
using these criteria, the promoter regions were run through the program, using the 5mc log <dig> ratio for the methylation score of each island .
of the  <dig> promoters,  <dig> were considered methylated and  <dig> were unmethylated.
this distribution is unsurprising considering that promoters which are methylated tend to silence the function associated with the gene.
the p-values calculated by the kolmogorov-smirnov test clearly show the significance between methylated and unmethylated cgis with all categories being notably less than  <dig>  as shown in table  <dig>
methylated and unmethylated promoter cgis were compared by sequence for average length, gc content , and obscpg/expcpg ratio.
p-values were determine using the kolmogorov-smirnov two-sample test.
the unmethylated islands show a normal distribution according to the z-scores; however, it is hard to discern any important findings from the methylated cgis.
this is possibly due to the lack of methylated islands in this dataset.
a larger count of methylated cgis might have provided some deeper insight into how they tend to be distributed throughout the genome.
looking at the allocation of island length, it is clear that most islands within promoters are somewhere in the range of  <dig> -  <dig> bp long.
with a larger set of methylated cgis, there might have been a more informative conclusion as to whether longer islands, such as those in promoters, are more susceptible to methylation.
cgi motifs
it is still widely unknown as to why certain cgis are more susceptible to dna methylation as compared to others.
the possibility that cgis, especially those located within promoter regions and covering tsss, contain motifs that are more likely to mutate or allow methylation has not yet been thoroughly researched.
to determine if any of the cgis contained similar motifs, meme was run on  <dig> of the total  <dig> methylated promoters to discover the top  <dig> most significant methylated sequence motifs.
the motifs were then checked against the entire  <dig> cgis by using the mast tool for alignment.
a similar experiment was performed for  <dig> randomly chosen unmethylated promoter cgis.
it is interesting to note that even from this small sample of cgis, a large percentage  of methylated islands contain the top motif; whereas, less than half of the unmethylated islands contain that same motif .
the third motif for methylated cgis contains the most surprising result showing that it was almost non-existant within the scanned unmethylated cgis as compared to the methylated promoters .
however, when looking at the unmethylated island motifs, both the methylated and unmethylated cgis have almost equal occurrences for the top  <dig> hits.
with a larger database of methylated cgis, a more significant result could be obtained in terms of the motifs found within the islands, especially the cgis that cover promoter regions and tsss.
discussion
in our work we designed a brand new cgi detection tool, cpg island detection  <dig> .
it uses a hidden-markov model and the viterbi algorithm to detect cgis within mammalian genomes.
the parameters of the model are estimated using the baum-welch algorithm and the final method of locating islands uses a sliding window of a size specified by the program user.
the tool provides a graphical user interface for users, allowing textbox entry and one click results.
even with the limitations in computational power, cpg island detection  <dig>  stood up well against the takai and jones cpg island searcher.
it was able to detect  <dig> cgis within human chromosome  <dig> and the average lengths and obscpg/expcpg ratios were in line with that of the takai and jones method,  <dig> bp and  <dig>  respectively.
a list of  <dig> promoters within chromosome  <dig> from weber et al.
was analyzed using the tool's analysis tab.
the methylation status was entered from the original data and after the tool's analysis some significant results were obtained.
there is a definite difference between methylated and unmethylated islands and the compositions of their characteristics  which all had p-values less than  <dig>  .
the z-score graph produced by the dataset showed that unmethylated cgis show a normal distribution as well.
a larger dataset of methylated islands is required in order to see if there is anything interesting in regards to how they are distributed.
finally, the  <dig> methylated promoter regions and another  <dig> unmethylated regions were run through meme and mast to determine if there are any significant motifs shared between cgis.
the methylated islands shared the  <dig> top motifs with percentages of  <dig> %,  <dig> %, and  <dig> % respectively; whereas, those motifs were only found in less than 50% of the unmethylated cgis.
the motifs found within the unmethylated islands were equally distributed throughout both the methylated and unmethylated regions.
this indicates a possible correlation between motifs and methylation in regards to gene silencing.
those genes more likely to become methylated may contain motifs prone to methylation and mutation.
CONCLUSIONS
using an entire genome analysis will provide better insight into the analysis of methylated and unmethylated islands.
a more recognizable distribution for methylated islands might be possible with a larger set of data points to consider.
acquiring more data will better showcase the power of the analysis tool and the assistance it provides to users scanning genomic regions for cgis.
the tool will be improved to allow a user to save their results and export the located cgis to a file for other experiments and analyses.
it will also be upgraded to allow a user to import located cgis from a previous session or file, rather than requiring a rescan of a sequence every time an analysis needs to be completed.
obtaining a larger number of methylated islands for analysis with meme and mast will provide more significant results in terms of motifs within cgis.
looking across the entire genome and the promoter regions found within a multitude of chromosomes could show whether the methylation-prone motifs are consistent within susceptible cgis across the genome and provide an insight into why certain genes become silenced within diseases such as cancer.
developing this new tool for the community using powerful algorithms has shown that combining analysis with cgi detection will improve the continued research within the field of epigenetics.
competing interests
the author declare that they have no competing interests.
authors' contributions
ls created the program and carried out the experiments.
nc provided advice and resources to perform all of the required tests and design the algorithm and helped draft the manuscript.
all authors read and approved the final manuscript.

 epigenetics studies the changes in gene function and gene expression that are not discernable by mutations in the dna sequence. the area of biology devoted to epigenetics is a recent development and has a large amount of room for growth with new research on cancer, mammalian gene expression, and technological advances constantly being brought forth from the community. epigenetic inheritance focuses on both mitotic and meiotic cellular changes and the processes involved. looking at cell differentiation and genetic imprinting through epigenetics has created new leads for cancer research in terms of tumour growth. the chromatin that controls dna processes is an epigenetic mechanism in either an active or repressive state. there are three main mechanisms in epigenetics: dna methylation, histone modifications, and the binding of non-histone proteins. cpg islands usually appear at the 5’ end of genes containing gc-rich dinucleotides. normally, these regions are unmethylated; however, when methylation occurs, gene regulation is affected and methylation sometimes leads to carcinogenesis. the importance of cgis has produced numerous algorithms throughout the community dedicated to locating and understanding these regions in dna. many of the traditional algorithms use the measures of length, gc content, and the number of observed over expected cpgs when determining if a section of dna is a cgi. however, some newer algorithms employ a distance based detection method to identify cpg clusters. some of the features of unmethylated cpgs are their affinity to bind to a protein domain, their low mutation rate, and their association with open chromatin. low methylation frequency has been correlated with high cpg density and vice versa. dna methylation refers to the replacement of the attached hydrogen with a methyl group on a cytosine base, which causes the chromatin to become more compact affecting transcription factor binding. methylated cytosines will produce thymine when deaminated unlike unmethylated cytosines which produce uracil. cpg density is lost due to the thymine mutation and this often inhibits the promoter regions of genes. the affect of methylation is particularly important in the case of cancer and the epigenetic modifications that silence tumour suppressor genes. it has been observed that genes silenced epigenetically share sequence motifs in their promoter regions. this is one of the possible ways to detect cancer hypermethylation. in genetics, a sequence motif is a short pattern of nucleotides that is deemed to have biological significance. if a motif appears in the exonic region of a gene, it may encode the structural motif of a specific protein. regulatory sequence motifs are located in areas where regulatory proteins such as transcription factors bind to the dna. in order to find the most significant motifs in dna, many algorithms have been designed and applied to different organisms. when describing a motif, pattern notation using regular expressions is what depicts the sequence. the de novo computational methods to discover important motifs take multiple input sequences and try to generate candidate motifs. two of the most well-known algorithms often used by many researchers are blast and meme. cpg islands are found in 40% of promoter and exonic regions of mammalian genes. other areas of the genome contain very few cpg dinucleotides and these areas are normally methylated. methylation of promoter cpgs is known to cause gene silencing and is heavily implicated in carcinogenesis. gardener-garden and frommer were the first researchers to use computational methods to detect and analyze cpg islands using specific criteria: 200-bp length dna region, gc content greater than 50%, and observed cpg/expected cpg ratio greater than. although the original criteria provided a good starting point for cpg island detection, it didn’t take into account repeating regions of dna. alu repeats are short interspersed elements repeating within the genome that are approximately 280-bp in length often containing a high gc content and obscpg/expcpg ratio. takai and jones analyzed human chromosomes and for cpg islands using their own algorithm that built upon the original criteria coined by gardener-garden and frommer. the new algorithm reduced the number of detected cpg islands from to, which is closer to the number of genes located on the two chromosomes. using the same criteria, the new algorithm modifies the constraints of each criterion to produce better detection results. now repeating elements such as alu are not considered as often as before. the constraints for the new algorithm are as follows: length ≥ 500-bp, gc content ≥ 55%, and obscpg/expcpg ≥. cpgcluster discovers clusters of cpgs by looking at the distance between other cpgs on the same chromosome and applying statistical significance. the two algorithms were compared using many different factors to determine which is better at finding cgis. cpgcluster locates a much larger number of cgis; however, after further analysis only % and % mapped to promoter regions of the human and mouse genomes respectively. the study found that often multiple clusters of cpgs from cpgcluster were substrings of one large cgi detected by the takai and jones algorithm. since there is no length limitation when cpgcluster detects cgis, a much larger number of clusters are discovered. gene expression is one of the most important functions in all forms of life. transcription factors are encoded in about 3-5% of genes in eukaryotes allow the repression or activation of specific genes within dna. chromatin plays another significant role in gene regulation and the network of interactions between transcription factors and chromatin structure is becoming increasingly important in epigenetic research. dna methylation is an epigenetic memory mechanism involved in the silencing of genes within eukaryotic organisms. histone modifications are another instrument in the epigenetic inheritance that passes information from parent to daughter cells. post-translational modifications of core histone proteins have been linked to transcription repression and activation. aberrant methylation of promoter regions of genes has been linked to gene silencing and loss of expression in diseases like cancer and it is known that cancer mutation can cause alterations to protein signaling genes. single nucleotide polymorphisms are the most common variation in the genetic sequence of the human genome. studies continue to provide an increasing amount of evidence that snps are correlated with cancer and can be used as indicators of the disease. analyzing sequence variants in motifs within promoter regions of methylated genes could provide significant disease markers and possible sites for therapeutic study. in this study, we examine several problems related to cpg islands and dna methylation of the promoter regions of genes: • design a method of cgi detection using powerful algorithms that improves performance while incorporating the ability to correlate the methylation status of the dna with the location of the cgi. • incorporate the power of analysis alongside cgi detection for an all-in-one program that covers the needs of the community. • integrate motif finding into the detection algorithm, determine if the motifs are within cgis, and verify if they are within a transcriptional start site. the rest of the paper is organized as follows. we first present the conceptual framework on which the program was designed. then the methodology of the finalized program is discussed. finally, the first set of experiments is presented. methods the detection of cgis has evolved since the first detection algorithm was proposed by gardener-garden and frommer. recently, studies have shown that incorporating the use of a hidden markov model in a detection algorithm can improve results. when establishing new techniques, it is still important to consider the traditional methods and integrate the best features of both into a new algorithm. in our work, we combined a hidden markov model, the baum-welch algorithm, and the viterbi algorithm along with the traditional sliding window criteria to lower the detection of repeating elements. hidden markov model a hidden markov model consists of a markov process in which the state is unobservable. a markov process is a random phenomenon where future probabilities are determined based on the most recent values. an hmm requires the knowledge of a few probabilities before it can be run on any data. these probabilities are split into three separate groups: • initial probabilities - the probabilities that determine which state the system will be in during the start of the algorithm. often, the initial probabilities are equal among the different states =, p = ). • transition probabilities - the probabilities that provide the occurrence of a change from state i to state j =, p = ). • emission probabilities - the probabilities distinguishing each state based on the observations of the system =, p = ). estimating parameters hmms have three distinct sets of parameters or probabilities: the initial state probabilities that determine which state the system starts in; the transition probabilities that decide if the state will switch after a certain period of time; and the emission probabilities showing whether the current symbol output belongs to one state or another. for an hmm to decode a sequence into a path of states, the parameters need to be trained on a sequence of symbols to detect the final probabilities the system will use when finding the viterbi path. one of the best and most efficient methods of estimating probabilities is through the use of the baum-welch algorithm, which is a special case of expectation-maximization. the baum-welch algorithm is often used in hmms to estimate the unknown parameters or probabilities. it is also known as the forward-backwards algorithm and is a special case of the generalized expectation-maximization algorithm. it can produce maximum likelihood and posterior mode estimates for model parameters when given only the emission probabilities to work with. the algorithm starts by assigning initial probabilities to all of the model parameters. then it continues until convergence happens by adjusting the probabilities of each model parameter to increase the probability of the model in accordance with the training set being scanned. viterbi algorithm the viterbi algorithm uses dynamic programming to find the most likely sequence that the hidden states would take based on the observations in a parameterized model. this sequence is called the viterbi path and it is usually related to hmms. the viterbi algorithm is very similar to the forward algorithm which computes the probability that a set of observed events was generated by the model. the algorithm was designed in by andrew viterbi to decode convolutional codes within the noise of digital communication links. the algorithm takes a hmm with possible q states, initial probabilities πi where i is the current state of the model, and transition probabilities ai,j where i, j is the change from state i to state j. given a sequence of observable data x …,xl, the algorithm will generate a state sequence q …,ql for each observable value. the algorithm produces the final output using recurrence relations. vl,k is the probability of the most likely state sequence based on the current l + observations. the state sequence can be recovered by saving in memory the state q is in during the run through the second equation. then say there is a function, st that returns the value of q which produced vl,k when l > and k when l = the viterbi path can be discovered using the following: dna methylation analysis once the cgi detection algorithm runs and scans the genetic sequence, the researcher can use the detected island locations to create primer sequences to determine the methylation status of the cgi. often, a separate statistics program is used to calculate significance. in our work, the analysis of the data is available using the p-value derived from the kolmogorov-smirnov two-sample test and the distribution of methylated to unmethylated islands is tabulated through the calculation of the z-score. the kolmogorov-smirnov test uses minimum distance estimation to compare sample datasets with reference probability distributions equating them with a one-dimensional probability distribution. the test can be performed with one sample dataset or with two sample datasets. the test either defines the mathematical distance between the empirical distribution function of a set of data and the cumulative distribution function of the reference distribution or the distance between the empirical distribution of two separate sets of data. the samples calculated under the null hypothesis are taken from the reference distribution or the same distribution and form the null distribution for the test. when the kolmogorov-smirnov test is used as a goodness of fit test, the data is normalized and compared to a standard normal distribution. the kolmogorov-smirnov statistic uses the empirical distribution function where are a set of ordered data points, where 1{yi ≤ x} is the indicator function. the kolmogorov statistic for a cumulative distribution function e can be calculated using, which calculates the supremum of the distances in the set, sup x. the kolmogorov-smirnov statistic often requires a large set of data to give an accurate acceptance or rejection of the null hypothesis; however, since we are working with the human genome and chromosomes seem to contain a large amount of cgis and thus our datasets should be large enough to produce accurate p-values. in our work, we use the two-sample k-s test to determine if two datasets differ in their probability distributions in regards to length, gc content, and obs/exp ratio. the two-sample k-s test uses the kolmogorov statistic where and are the empirical distribution functions of each sample. program architecture there are a multitude of detection programs that use many different algorithms to accurately detect cgis within a genetic sequence. some of the most popular cgi detection algorithms are gardener-garden and frommer, cpg island searcher, and cpgprod. the gardener-garden and frommer algorithm is the original cgi detection algorithm which uses a sliding window of bp along with a gc content greater than 50% and an observed-to-expected cpg ratio greater than. the cpg island searcher built upon the original foundation using a window of bp, gc content ≥ 55%, and obscpg/expcpg ≥. the cpgprod algorithm searches a genome for cgis using two steps: search for all cgis in a submitted sequence based of the traditional criteria, and predict the orientation of promoters once the start cgi is discovered. we decided to design a graphical user interface for our cgi detection program to provide accessibility for researchers that are not well-versed in scripting or working with programs depending on the command prompt. while both the cpg island searcher and cpgprod have a web server that provides a user interface, it is not feasible to run an dataset as large as a human chromosome through the web. both programs must be run using typed commands and parameters if not running them through the web and do not provide the same interface as on the web for the user. layout and design the original cgi detection layout and code was released by tanner helland under the bsd license. it was originally written and designed in microsoft visual basic, but we updated and modified the code using microsoft visual basic.net and microsoft visual studio the gui provides an intuitive method for loading the fasta sequence file, setting up the hmm parameters, estimating the parameters based on the file, and running the algorithm. once the viterbi algorithm has defined when the sequence is in an island state or a normal state, the sliding window can be run to detect where the islands are located within the genomic sequence which show inside the graphs for obscpg/expcpg ratio and i/b ratio. once the sliding window has scanned for cgis, the results are shown in the textbox to the right. we modified the layout to use a tab control in order to switch between the cgi detection and the analysis of the results. the analysis tab contains a small spreadsheet for the detected islands where the user can change the methylation status and can enter a methylation score for each island. methylation scores have been used in many different studies as a measure of the strength of the methylation of a specific cgi to determine whether to classify it as methylated or unmethylated. once the user has filled in the values for methylation status and score for each cgi, the analysis of the data can be completed. the table next to the spreadsheet displays the separate mean values for cgi length, gc content, and obscpg/expcpg ratio for the unmethylated and methylated cgis. the p-values are calculated using the kolmogorov-smirnov two-sample test. the chart underneath the spreadsheet displays the z-score distribution for the methylated and unmethylated cgis determined by using the methylation scores entered by the user. the final chart shows the distribution of lengths of the cgis across the two sets of data. we created this layout and design to provide practicality for users that are not computational experts and to offer an all-in-one solution for detecting and analyzing cgi data.  methylation analysis looking at the composition of cgis when methylated and unmethylated is important in the study of the epigenetic mechanism of methylation. the list of promoters from weber et al. was evaluated by taking the promoters found within chromosome and analyzing them using the cpg island detection program analysis tab. the promoters were selected based on the promoter class given to each in the previous work. those with a class of hcp or icp were considered to contain cgis within or covering the promoter region when looking at methylation. a cgi was considered methylated if the 5mc log ratio and unmethylated otherwise. using these criteria, the promoter regions were run through the program, using the 5mc log ratio for the methylation score of each island. of the promoters, were considered methylated and were unmethylated. this distribution is unsurprising considering that promoters which are methylated tend to silence the function associated with the gene. the p-values calculated by the kolmogorov-smirnov test clearly show the significance between methylated and unmethylated cgis with all categories being notably less than as shown in table methylated and unmethylated promoter cgis were compared by sequence for average length, gc content, and obscpg/expcpg ratio. p-values were determine using the kolmogorov-smirnov two-sample test. the unmethylated islands show a normal distribution according to the z-scores; however, it is hard to discern any important findings from the methylated cgis. this is possibly due to the lack of methylated islands in this dataset. a larger count of methylated cgis might have provided some deeper insight into how they tend to be distributed throughout the genome. looking at the allocation of island length, it is clear that most islands within promoters are somewhere in the range of - bp long. with a larger set of methylated cgis, there might have been a more informative conclusion as to whether longer islands, such as those in promoters, are more susceptible to methylation. cgi motifs it is still widely unknown as to why certain cgis are more susceptible to dna methylation as compared to others. the possibility that cgis, especially those located within promoter regions and covering tsss, contain motifs that are more likely to mutate or allow methylation has not yet been thoroughly researched. to determine if any of the cgis contained similar motifs, meme was run on of the total methylated promoters to discover the top most significant methylated sequence motifs. the motifs were then checked against the entire cgis by using the mast tool for alignment. a similar experiment was performed for randomly chosen unmethylated promoter cgis. it is interesting to note that even from this small sample of cgis, a large percentage of methylated islands contain the top motif; whereas, less than half of the unmethylated islands contain that same motif. the third motif for methylated cgis contains the most surprising result showing that it was almost non-existant within the scanned unmethylated cgis as compared to the methylated promoters. however, when looking at the unmethylated island motifs, both the methylated and unmethylated cgis have almost equal occurrences for the top hits. with a larger database of methylated cgis, a more significant result could be obtained in terms of the motifs found within the islands, especially the cgis that cover promoter regions and tsss. discussion in our work we designed a brand new cgi detection tool, cpg island detection. it uses a hidden-markov model and the viterbi algorithm to detect cgis within mammalian genomes. the parameters of the model are estimated using the baum-welch algorithm and the final method of locating islands uses a sliding window of a size specified by the program user. the tool provides a graphical user interface for users, allowing textbox entry and one click results. even with the limitations in computational power, cpg island detection stood up well against the takai and jones cpg island searcher. it was able to detect cgis within human chromosome and the average lengths and obscpg/expcpg ratios were in line with that of the takai and jones method, bp and respectively. a list of promoters within chromosome from weber et al. was analyzed using the tool's analysis tab. the methylation status was entered from the original data and after the tool's analysis some significant results were obtained. there is a definite difference between methylated and unmethylated islands and the compositions of their characteristics which all had p-values less than. the z-score graph produced by the dataset showed that unmethylated cgis show a normal distribution as well. a larger dataset of methylated islands is required in order to see if there is anything interesting in regards to how they are distributed. finally, the methylated promoter regions and another unmethylated regions were run through meme and mast to determine if there are any significant motifs shared between cgis. the methylated islands shared the top motifs with percentages of %, %, and % respectively; whereas, those motifs were only found in less than 50% of the unmethylated cgis. the motifs found within the unmethylated islands were equally distributed throughout both the methylated and unmethylated regions. this indicates a possible correlation between motifs and methylation in regards to gene silencing. those genes more likely to become methylated may contain motifs prone to methylation and mutation.  using an entire genome analysis will provide better insight into the analysis of methylated and unmethylated islands. a more recognizable distribution for methylated islands might be possible with a larger set of data points to consider. acquiring more data will better showcase the power of the analysis tool and the assistance it provides to users scanning genomic regions for cgis. the tool will be improved to allow a user to save their results and export the located cgis to a file for other experiments and analyses. it will also be upgraded to allow a user to import located cgis from a previous session or file, rather than requiring a rescan of a sequence every time an analysis needs to be completed. obtaining a larger number of methylated islands for analysis with meme and mast will provide more significant results in terms of motifs within cgis. looking across the entire genome and the promoter regions found within a multitude of chromosomes could show whether the methylation-prone motifs are consistent within susceptible cgis across the genome and provide an insight into why certain genes become silenced within diseases such as cancer. developing this new tool for the community using powerful algorithms has shown that combining analysis with cgi detection will improve the continued research within the field of epigenetics. competing interests the author declare that they have no competing interests. authors' contributions ls created the program and carried out the experiments. nc provided advice and resources to perform all of the required tests and design the algorithm and helped draft the manuscript. all authors read and approved the final manuscript. 
developing this new tool for the community using powerful algorithms has shown that combining analysis with cgi detection will improve the continued research within the field of epigenetics. our solution provides a graphical user interface not seen in many of the other cgi detection programs and we unify the detection and analysis under one program to allow researchers to scan a genetic sequence, detect the significant cgis, and analyze the sequence once the scan is complete for any noteworthy findings. we propose a new detection program using a hidden-markov model alongside the viterbi algorithm. cpg islands are important regions in dna. they usually appear at the 5’ end of genes containing gc-rich dinucleotides. when dna methylation occurs, gene regulation is affected and it sometimes leads to carcinogenesis.
 cpg islands are important regions in dna. they usually appear at the 5’ end of genes containing gc-rich dinucleotides. when dna methylation occurs, gene regulation is affected and it sometimes leads to carcinogenesis. we propose a new detection program using a hidden-markov model alongside the viterbi algorithm. methods our solution provides a graphical user interface not seen in many of the other cgi detection programs and we unify the detection and analysis under one program to allow researchers to scan a genetic sequence, detect the significant cgis, and analyze the sequence once the scan is complete for any noteworthy findings.  using human chromosome we show that our algorithm finds a significant number of cgis. running an analysis on a dataset of promoters discovered that the characteristics of methylated and unmethylated cgis are significantly different. finally, we detected significantly different motifs between methylated and unmethylated cgi promoters using meme and mast.  developing this new tool for the community using powerful algorithms has shown that combining analysis with cgi detection will improve the continued research within the field of epigenetics. 18- december ieee international conference on bioinformatics and biomedicine hong kong, p. r. china 