String comparison by transposition networks
Krusche, Peter and Tiskin, Alexander (2009) String comparison by transposition networks. In: London Algorithmics 2008: Theory and Practice. London: College Publications, pp. 184-204. ISBN 9781904987970
Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Official URL: http://www.collegepublications.co.uk/algorithmics/...
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|
|Place of Publication:||London|
|Book Title:||London Algorithmics 2008: Theory and Practice|
|Official Date:||1 June 2009|
|Page Range:||pp. 184-204|
|Status:||Not Peer Reviewed|
|Access rights to Published version:||Restricted or Subscription Access|
A volume dedicated to Maxime Crochemore on his 60th birthday.
|Open Access Version:|
Actions (login required)