Blind Clustering of DNA Fragments Based on Kullback-Leibler Divergence

In whole genome shotgun sequencing when DNA fragments are derived from thousands of microorganisms in the environment sample, traditional alignment methods are impractical to use because of their high computation complexity. In this paper, we take the divergence vector which is consist of Kullback-Leibler divergences of different word lengths as the feature vector. Based on this, we use BP neural network to identify whether two fragments are from the same microorganism and obtain the similarity between fragments. Finally, we develop a new novel method to cluster DNA fragments from different microorganisms into different groups. Experiments show that it performs well.

Authors and Affiliations

1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, 1954 Hua Shan Rd., Shanghai, 200030, China

   Xiongjun Pi, Wenlu Yang & Liqing Zhang

2. Shanghai Institute for Systems Biology, Shanghai Jiao Tong University,  

   Xiongjun Pi

Editors and Affiliations

1. School of Electrical and Electronic Engineering, Nanyang Technological University, Block S1, Nanyang Avenue, 639798, Singapore

   Lipo Wang

2. School of Software, Sun Yat-Sen University, 510275, Guangzhou, China

   Ke Chen

3. School of Computer Engineering, Nanyang Technological University, BLK N4, 2b-39, Nanyang Avenue, 639798, Singapore

   Yew Soon Ong

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics