Clustering genome data based on approximate matching

Nagamma Patil, Durga Toshniwal and Kumkum Garg

International Journal of Data Analysis Techniques and Strategies, 2013, vol. 5, issue 2, 122-147

Abstract: Genome data mining and knowledge extraction is an important problem in bioinformatics. Some research work has been done for genome identification based on exact matching of n-grams. However, in most real world biological problems, it may not be feasible to have an exact match, so approximate matching may be desired. The problem in using n-grams is that the number of features (4ⁿ for DNA sequence and 20ⁿ for protein sequence) increases with increase in n. In this paper, we propose an approach for genome data clustering based on approximate matching. Generally genome sequences are very long, so we sample the data into 10,000 base pairs. Given a database of genome sequences, our proposed work includes extraction of total number of approximate matching patterns to a query with given fault tolerance and then using this total number of matches for clustering. Candidate length is varied so as to allow both positive and negative tolerance and hence the number of features used for clustering also varies. K-means, fuzzy C-means (FCM) and possibilistic C-means (PCM) algorithms are used for clustering of the genome data. Experimental results obtained by varying tolerance from 20% to 70% are reported. It has been observed that as tolerance increases, number of genome samples that are correctly clustered also increases and our proposed approach outperforms existing n-gram frequency based approach. Two different genome datasets are used to verify the proposed method namely yeast, E. coli and Drosophila, mouse.

Keywords: bioinformatics; soft computing; genome data; data mining; pattern matching; exact matching; approximate matching; data clustering; knowledge extraction; DNA sequences; protein sequences; fault tolerance; K-means clustering; fuzzy C-means clustering; FCM; possibilistic C-means clustering; PCM; E. coli; Drosophila; biomedicine. (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=53678 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:injdan:v:5:y:2013:i:2:p:122-147

Access Statistics for this article

More articles in International Journal of Data Analysis Techniques and Strategies from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().