Limits...
A gene pattern mining algorithm using interchangeable gene sets for prokaryotes.

Hu M, Choi K, Su W, Kim S, Yang J - BMC Bioinformatics (2008)

Bottom Line: These algorithms use the optimization problem formulation which is solved using the dynamic programming technique.In an experiment with four newly sequenced genomes (where the gene annotation is unavailable), we show that the gene pattern can capture important biological information.The discovered gene patterns can be used for the detecting of ortholog and genes that collaborate for a common biological function.

View Article: PubMed Central - HTML - PubMed

Affiliation: EECS, Case Western Reserve University, Cleveland, OH 44106 USA. meng.hu@case.edu

ABSTRACT

Background: Mining gene patterns that are common to multiple genomes is an important biological problem, which can lead us to novel biological insights. When family classification of genes is available, this problem is similar to the pattern mining problem in the data mining community. However, when family classification information is not available, mining gene patterns is a challenging problem. There are several well developed algorithms for predicting gene patterns in a pair of genomes, such as FISH and DAGchainer. These algorithms use the optimization problem formulation which is solved using the dynamic programming technique. Unfortunately, extending these algorithms to multiple genome cases is not trivial due to the rapid increase in time and space complexity.

Results: In this paper, we propose a novel algorithm for mining gene patterns in more than two prokaryote genomes using interchangeable sets. The basic idea is to extend the pattern mining technique from the data mining community to handle the situation where family classification information is not available using interchangeable sets. In an experiment with four newly sequenced genomes (where the gene annotation is unavailable), we show that the gene pattern can capture important biological information. To examine the effectiveness of gene patterns further, we propose an ortholog prediction method based on our gene pattern mining algorithm and compare our method to the bi-directional best hit (BBH) technique in terms of COG orthologous gene classification information. The experiment show that our algorithm achieves a 3% increase in recall compared to BBH without sacrificing the precision of ortholog detection.

Conclusion: The discovered gene patterns can be used for the detecting of ortholog and genes that collaborate for a common biological function.

Show MeSH
Accuracy of DISPattern w.r.t. support. Different support thresholds yield different sets of DISPattern. By applying these different sets of patterns, different gene annotations may be obtained. This figure shows the recall and precision of the gene annotation w.r.t. the support threshold. Since each gene is assigned to one group, the precision is the same as the recall.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2279103&req=5

Figure 2: Accuracy of DISPattern w.r.t. support. Different support thresholds yield different sets of DISPattern. By applying these different sets of patterns, different gene annotations may be obtained. This figure shows the recall and precision of the gene annotation w.r.t. the support threshold. Since each gene is assigned to one group, the precision is the same as the recall.

Mentions: In the gene pattern mining algorithm, Tsup is the support threshold which defines frequent patterns. Varying the support threshold will vary the number of patterns discovered. The lower the Tsup value is, the more patterns will be discovered. The recall and precision of our proposed ortholog discovery approach change with different support thresholds Tsup, which is plotted in figure 2. In this test, a gene is mapped to one ortholog group, thus the recall is equal to the precision.


A gene pattern mining algorithm using interchangeable gene sets for prokaryotes.

Hu M, Choi K, Su W, Kim S, Yang J - BMC Bioinformatics (2008)

Accuracy of DISPattern w.r.t. support. Different support thresholds yield different sets of DISPattern. By applying these different sets of patterns, different gene annotations may be obtained. This figure shows the recall and precision of the gene annotation w.r.t. the support threshold. Since each gene is assigned to one group, the precision is the same as the recall.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2279103&req=5

Figure 2: Accuracy of DISPattern w.r.t. support. Different support thresholds yield different sets of DISPattern. By applying these different sets of patterns, different gene annotations may be obtained. This figure shows the recall and precision of the gene annotation w.r.t. the support threshold. Since each gene is assigned to one group, the precision is the same as the recall.
Mentions: In the gene pattern mining algorithm, Tsup is the support threshold which defines frequent patterns. Varying the support threshold will vary the number of patterns discovered. The lower the Tsup value is, the more patterns will be discovered. The recall and precision of our proposed ortholog discovery approach change with different support thresholds Tsup, which is plotted in figure 2. In this test, a gene is mapped to one ortholog group, thus the recall is equal to the precision.

Bottom Line: These algorithms use the optimization problem formulation which is solved using the dynamic programming technique.In an experiment with four newly sequenced genomes (where the gene annotation is unavailable), we show that the gene pattern can capture important biological information.The discovered gene patterns can be used for the detecting of ortholog and genes that collaborate for a common biological function.

View Article: PubMed Central - HTML - PubMed

Affiliation: EECS, Case Western Reserve University, Cleveland, OH 44106 USA. meng.hu@case.edu

ABSTRACT

Background: Mining gene patterns that are common to multiple genomes is an important biological problem, which can lead us to novel biological insights. When family classification of genes is available, this problem is similar to the pattern mining problem in the data mining community. However, when family classification information is not available, mining gene patterns is a challenging problem. There are several well developed algorithms for predicting gene patterns in a pair of genomes, such as FISH and DAGchainer. These algorithms use the optimization problem formulation which is solved using the dynamic programming technique. Unfortunately, extending these algorithms to multiple genome cases is not trivial due to the rapid increase in time and space complexity.

Results: In this paper, we propose a novel algorithm for mining gene patterns in more than two prokaryote genomes using interchangeable sets. The basic idea is to extend the pattern mining technique from the data mining community to handle the situation where family classification information is not available using interchangeable sets. In an experiment with four newly sequenced genomes (where the gene annotation is unavailable), we show that the gene pattern can capture important biological information. To examine the effectiveness of gene patterns further, we propose an ortholog prediction method based on our gene pattern mining algorithm and compare our method to the bi-directional best hit (BBH) technique in terms of COG orthologous gene classification information. The experiment show that our algorithm achieves a 3% increase in recall compared to BBH without sacrificing the precision of ortholog detection.

Conclusion: The discovered gene patterns can be used for the detecting of ortholog and genes that collaborate for a common biological function.

Show MeSH