Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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] 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/...

Request Changes to record.

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:
DateEvent
1 June 2009Published
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:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us