Runtime Needleman-Wunsch & Gotoh

I have a question regarding the runtime & memory space with

Needleman-Wunsch: A sequence with 1000 characters needs 1 second & 32 MB - how long & how much a 2000 character sequence?
Gotoh: same instructions

I know that runtime of Needleman-Wunsch is O=(n^2), but do i need to square the ratio?

gotoh needleman-wunsch runtime

• 4,292 views • link

updated 4.3 years ago by Ram

• written 11.5 years ago by sarah-spie •

depends on the implementation of Needleman-Wunsch algorithm (language, platform,...)

• 0 views • link

updated 4.3 years ago by Ram

• written 11.5 years ago by Nicolas Rosewick

Don't bother... it's a homework assignment.

• 0 views • link

updated 4.3 years ago by Ram

• written 11.5 years ago by Brian Bushnell

1 answer

Well here is a nice writeup:

Improvements in time and memory efficiency for global alignments

http://www.bioinformaticsonline.org/ch/ch03/supp-3.html

(even if this is a homework getting the answer from the page above support the learning process ;-) )

• 0 views • link

updated 4.8 years ago by Ram

• written 11.5 years ago by Istvan Albert

More posts like this

Conservation scores at each location of few motifs in MSA
written 2.2 years ago by wannabio •

I am currently working on a bioinformatics problem where I need to lookup and count the location and count of occurences of 4000-ish 5 character …
Problem with memory requirements for SPades
written 6.6 years ago by Tospohh •

I am trying to assemble **Illumina MiSeq paired-end reads** from two **Plasmodium falciparum** samples. The genome is only about *20Mb* long. The two samples are …
Generating artificial NGS reads from a FASTA file specifying read length, coverage, and start seque…
written 7.4 years ago by Hamish •

I am looking to generate artificial single-end Illumina sequencing data from a FASTA containing a number of short sequences representing unique molecular identifiers. However, I've …
Dendrogram on SNPs from VCF file?
written 7.5 years ago by popescuiofelia •

Hi! I have tried making a dendrogram from a VCF file that contains SNP data for 20 samples. First, I tried the SNP relate software, …
Tool: repaq: compress Illumina FASTQ to be as small as 1/4 of the gzip format.
written 8.0 years ago by chen

`repaq` is an open source tool for FASTQ compression: https://github.com/OpenGene/repaq It repacks Illumina format FASTQ to a smaller binary file (.rfq), which can be further …
Approach to sequence alignment for long strings
written 9.1 years ago by dustin.farkas.yo •

Hello, I am trying to use sequence alignment tools to align two text strings of length 500,000. I tried using the pairwise2 package from Biopython …
Using the ABySS pipeline to scaffold a DISCOVAR de novo assembly
written 10.7 years ago by dbrowne.up •

Hi all, I have a DISCOVAR de novo assembly that was made with 2x250 bp paired end reads with a fragment size of ~800. Since …
Blog: Masking low-complexity regions using pyfaidx MutableFastaRecord
written 11.7 years ago by Matt Shirley

I've added a new feature to my [pyfaidx][1] Python module which, in addition to current object-based random access to indexed Fasta files, allows the user …
Usage of Perl Needleman/Wunsch Module
written 12.1 years ago by biolab

Dear all, I installed Needleman-Wunsch module, however have some problems to handle it. Could anyone help to write **a simple example** to illustrate how to …
Tutorial: Transforming And Manipulating Color Space Reads
written 14.3 years ago by Istvan Albert

*This document is part of the lecture series on Next Generation Sequencing offered by the [Bioinformatics Consulting Center at Penn State][1]* Sequencing instruments that operate …