Skip to main navigation Skip to search Skip to main content

A space efficient algorithm for finding the best non-overlapping alignment score

  • Gary Benson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

Repeating patterns make up a significant fraction of DNA and protein molecules. These repeating regions are important to biological function because they may act as catalytic, regulatory or evolutionary sites and because they have been implicated in human disease. Additionally, these regions often serve as useful laboratory tools for such tasks as localizing genes on a chromosome and DNA fingerprinting. In this paper, we present a space eg~icient algorithm for finding the maximum alignment score for any two substrings of a single string T under the condition that the substrings do not overlap. In a biological context, this corresponds to the largest repeating region in the molecule. The algorithm runs in O(n2 log2 n) time and uses only O(n2) space.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings
EditorsMaxime Crochemore, Dan Gusfield
PublisherSpringer Verlag
Pages1-14
Number of pages14
ISBN (Print)9783540580942
DOIs
StatePublished - 1994
Externally publishedYes
Event5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994 - Asilomar, United States
Duration: 5 Jun 1994 → 8 Jun 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994
Country/TerritoryUnited States
CityAsilomar
Period5/06/94 → 8/06/94

Fingerprint

Dive into the research topics of 'A space efficient algorithm for finding the best non-overlapping alignment score'. Together they form a unique fingerprint.

Cite this