Bioinformatics Vol. 15 no. 12 1999
Pages 1012-1019
© 1999 Oxford University Press
Post-processing long pairwise alignments
1 Department of Computer Science and
Engineering, The Pennsylvania State University, University Park, PA
16802, USA
2 IMB Jena, Department of Genome Analysis,
P.O. Box 100 813, D-07708 Jena, Germany
Current address: Max Planck Institute for Chemical Ecology, Department of Molecular Genetics and Evolution, Tatzendpromenade 1a, 07745 Jena, Germany.
To whom correspondence should be addressed.
Motivation: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments.
Results: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment’s length. Practical applications to alignments of genomic DNA sequences are described.
Availability: Software is available at http://globin.cse.psu.edu/
Contact: webb{at}cse.psu.edu
Received on February 12, 1999
; revised on May 20, 1999
; accepted on June 4, 1999
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Csuros, J. A. Holey, and I. B. Rogozin In search of lost introns Bioinformatics, July 1, 2007; 23(13): i87 - i96. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Szklarczyk and J. Heringa AuberGene--a sensitive genome alignment tool Bioinformatics, June 15, 2006; 22(12): 1431 - 1436. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. N. Arslan and O. Egecioglu Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints INFORMS Journal on Computing, January 1, 2004; 16(4): 441 - 458. [Abstract] [PDF]
|
|
|
|
 |
|
 S. Schwartz, W. J. Kent, A. Smit, Z. Zhang, R. Baertsch, R. C. Hardison, D. Haussler, and W. Miller Human-Mouse Alignments with BLASTZ Genome Res., January 1, 2003; 13(1): 103 - 107. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. Onyango, W. Miller, J. Lehoczky, C. T. Leung, B. Birren, S. Wheelan, K. Dewar, and A. P. Feinberg Sequence and Comparative Analysis of the Mouse 1-Megabase Region Orthologous to the Human 11p15 Imprinted Domain Genome Res., November 1, 2000; 10(11): 1697 - 1710. [Abstract] [Full Text]
|
|