Subject: Computer and information sciences
Year: 2012
Type: Article
Type: PeerReviewed
Title: A new, space-efficient local pairwise alignment methodology
Author: Stojanov, Done
Author: Mileva, Aleksandra
Author: Koceski, Saso
Abstract: Aligning large nucleotide sequences requires significant portion of the memory, what in some cases is found as a limiting factor. Local pairwise alignment methods require O(m) space, most of them being dynamic programming-based. In this paper we present a new, space-efficient methodology and an algorithm for optimal un-gapped local pairwise alignment, using non dynamic programming-based approach. A highest scoring un-gapped local alignment is found, identifying and combining exact nucleotide matching regions, shifting one of the sequences over the other. The number of shifts is score-dependent, what is a time complexity advantage. An implementation of the proposed methodology was tested on EMBL-EBI viroid genomes, always identifying an optimal un-gapped local alignment, requiring on average m/2 space.
Publisher: HIKARI LTD
Relation: https://eprints.ugd.edu.mk/107/
Identifier: oai:eprints.ugd.edu.mk:107
Identifier: Stojanov, Done and Mileva, Aleksandra and Koceski, Saso (2012) A new, space-efficient local pairwise alignment methodology. Advanced Studies in Biology, 4 (2). pp. 85-93. ISSN 1313-9495
