String comparison by transposition networks
| dc.creator | Krusche, Peter | |
| dc.creator | Tiskin, Alexander | |
| dc.date | 2009-03-20 | |
| dc.date.accessioned | 2026-07-07T12:54:51Z | |
| dc.date.available | 2026-07-07T12:54:51Z | |
| dc.description | 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. | |
| dc.description | Published in London Algorithmics 2008: Theory And Practice, to appear | |
| dc.identifier | https://arxiv.org/abs/0903.3579 | |
| dc.identifier | http://arxiv.org/abs/0903.3579 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/224081 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | String comparison by transposition networks | |
| dc.type | text |