The Library
String comparison by transposition networks
Tools
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
PDF
0903.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (223Kb) |
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, Engineering and Medicine > Science > Computer Science | ||||
Publisher: | College Publications | ||||
Place of Publication: | London | ||||
ISBN: | 9781904987970 | ||||
Book Title: | London Algorithmics 2008: Theory and Practice | ||||
Official Date: | 1 June 2009 | ||||
Dates: |
|
||||
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. |
||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |