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
DISPattern Algorithm. This figure is the Flowchart of DISPattern algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: DISPattern Algorithm. This figure is the Flowchart of DISPattern algorithm.

Mentions: The flowchart of the DISPattern algorithm is given in Figure 1. Three main phases of the DISPattern algorithm are explained in the remainder of this section.


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

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

DISPattern Algorithm. This figure is the Flowchart of DISPattern algorithm.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: DISPattern Algorithm. This figure is the Flowchart of DISPattern algorithm.
Mentions: The flowchart of the DISPattern algorithm is given in Figure 1. Three main phases of the DISPattern algorithm are explained in the remainder of this section.

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