The Library
String comparison by transposition networks
Tools
Tools
Tools
Krusche, Peter and Tiskin, Alexander (2009) String comparison by transposition networks. In: London Algorithmics 2008: Theory and Practice. College Publications, London, pp. 184-204. ISBN 9781904987970
Full text not available from this repository.
Official URL: http://www.collegepublications.co.uk/algorithmics/...
Abstract
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.
| Item Type: | Book Item |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Publisher: | College Publications |
| Place of Publication: | London |
| ISBN: | 9781904987970 |
| Book Title: | London Algorithmics 2008: Theory and Practice |
| Date: | 1 June 2009 |
| Volume: | 11 |
| Page Range: | pp. 184-204 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Description: | A Volume Dedicated to Maxime Crochemore on his 60th Birthday. |
| Related URLs: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47533 |
Actions (login required)
 |
View Item |
