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. London: College Publications, pp. 184-204. ISBN 9781904987970
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
0903.pdf Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 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 > 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: | |||||
| URI: | http://wrap.warwick.ac.uk/id/eprint/47533 |
Request changes or add full text files to a record
Actions (login required)
 |
View Item |
