Linked Life Data

8790471

Source:http://linkedlifedata.com/resource/pubmed/id/8790471

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
4
pubmed:dateCreated
1996-11-22
pubmed:abstractText
A dynamic-programming strategy for sequence alignment first proposed in 1975 by Dan Hirschberg can be adapted to yield a number of extremely space-efficient algorithms. Specifically, these algorithms align two sequences using only "linear space," i.e., an amount of computer memory that is proportional to the sum of the lengths of the two sequences being aligned. This paper begins by reviewing the basic idea, as it applies to the global (i.e., end-to-end) alignment of two DNA or protein sequences. Three of our recent extensions of the technique are then outlined. The first extension computes an optimal alignment subject to the constraint that each position, i, of the first sequence must be aligned somewhere between positions L[i] and U[i] of the second sequence, for given values of L and U. The second finds all aligned position pairs (i.e., potential columns of the alignment) that occur in an alignment whose score exceeds a given threshold. The third treats the case where each of the two sequences is allowed to be an alignment (e.g., a sequence of aligned pairs), using a sensitive scoring scheme. We also describe two linear-space methods for computing k best local (i.e., involving only a part of each sequence) alignments, where k > or = 1. One is a linear-space version of the algorithm of Waterman and Eggert (1987), and the other is based on the strategy proposed by Wilbur and Lipman (1983). Finally, we describe programs that implement various combinations of these techniques to provide a multisequence alignment method that is especially suited to handling a few very long sequences. The utility of these programs is illustrated by analysis of the locus control region of the beta-like globin gene cluster of several mammals.
pubmed:grant
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:chemical
pubmed:status
MEDLINE
pubmed:issn
1066-5277
pubmed:author
pubmed:issnType
Print
pubmed:volume
1
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
271-91
pubmed:dateRevised
2007-11-14
pubmed:meshHeading
pubmed:year
1994
pubmed:articleTitle
Recent developments in linear-space alignment methods: a survey.
pubmed:affiliation
Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.
pubmed:publicationType
Journal Article, Research Support, U.S. Gov't, P.H.S.