Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics

Details Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics

2004-04-20

arxiv.org/abs/cs/0404039v1

Computer Science

Computational Complexity

4 pages

Scientific paper

After reviewing unnormalized and normalized information distances based on incomputable notions of Kolmogorov complexity, we discuss how Kolmogorov complexity can be approximated by data compression algorithms. We argue that optimal algorithms for data compression with side information can be successfully used to approximate the normalized distance. Next, we discuss an alternative information distance, which is based on relative entropy rate (also known as Kullback-Leibler divergence), and compression-based algorithms for its estimation. Based on available biological and linguistic data, we arrive to unexpected conclusion that in Bioinformatics and Computational Linguistics this alternative distance is more relevant and important than the ones based on Kolmogorov complexity.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-55557