String comparison by transposition networks
| Autor: | Krusche, Peter, Tiskin, Alexander |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: Published in London Algorithmics 2008: Theory And Practice, to appear |
| Databáze: | arXiv |
| Externí odkaz: |
|