The Library
Permutation editing and matching via embeddings
Tools
UNSPECIFIED (2001) Permutation editing and matching via embeddings. In: 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), IRAKLION, GREECE, JUL 08-12, 2001. Published in: AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING, 2076 pp. 481-492. ISBN 3-540-42287-0. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to transform one such permutation to another can be used as a measure of their evolutionary distance. Motivated by such scenarios, we study problems of computing distances between permutations as well as matching permutations in sequences, and finding most similar permutation from a collection ("nearest neighbor").
We adopt a general approach: embed permutation distances of relevance into well-known vector spaces in an approximately distance-preserving manner, and solve the resulting problems on the well-known spaces. Our results are as follows:
We present the first known approximately distance preserving embeddings of these permutation distances into well-known spaces.
Using these embeddings, we obtain several results, including the first known efficient solution for approximately solving nearest neighbor problems with permutations and the first known algorithms for finding permutation distances in the "data stream" model.
We consider a novel class of problems called permutation matching problems which are similar to string matching problems, except that the pattern is a permutation (rather than a string) and present linear or near-linear time algorithms for approximately solving permutation matching problems; in contrast, the corresponding string problems take significantly longer.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-42287-0 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Orejas, F and Spirakis, PG and VanLeeuwen, J | ||||
Official Date: | 2001 | ||||
Dates: |
|
||||
Volume: | 2076 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 481-492 | ||||
Publication Status: | Published | ||||
Title of Event: | 28th International Colloquium on Automata, Languages and Programming (ICALP 2001) | ||||
Location of Event: | IRAKLION, GREECE | ||||
Date(s) of Event: | JUL 08-12, 2001 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |