String comparison by transposition networks

Details String comparison by transposition networks String comparison by transposition networks

2009-03-20

arxiv.org/abs/0903.3579v1

Computer Science

Data Structures and Algorithms

Published in London Algorithmics 2008: Theory And Practice, to appear

Scientific paper

Computing string or sequence alignments is a classical method of comparing strings and has applications in many areas of computing, such as signal processing and bioinformatics. Semi-local string alignment is a recent generalisation of this method, in which the alignment of a given string and all substrings of another string are computed simultaneously at no additional asymptotic cost. In this paper, we show that there is a close connection between semi-local string alignment and a certain class of traditional comparison networks known as transposition networks. The transposition network approach can be used to represent different string comparison algorithms in a unified form, and in some cases provides generalisations or improvements on existing algorithms. This approach allows us to obtain new algorithms for sparse semi-local string comparison and for comparison of highly similar and highly dissimilar strings, as well as of run-length compressed strings. We conclude that the transposition network method is a very general and flexible way of understanding and improving different string comparison algorithms, as well as their efficient implementation.

Affiliated with

Also associated with

No associations

Rating

String comparison by transposition networks 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 String comparison by transposition networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and String comparison by transposition networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642514