Software uninstalled from brew still on $PATH
Homebrew likes to create symlinks from /usr/local/bin/ to /usr/local/Cellar/. 

You can see if this is the case by running: ls -l /usr/local/bin/bowtie2.

That should return a line with arrow syntax (-&gt;) like this:

/usr/local/bin/bowtie2 -&gt; ../Cellar/bowtie2/&lt;someversion&gt;/bin/bowtie2


If that's the case, then you can just delete the broken symlink with: rm /usr/local/bin/bowtie2 (you may need to preface that with sudo depending on ownership of /usr/local/bin/. It's the broken symlink that is causing which to still show bowtie2 as being located in /usr/local/bin/.

You can then move the new binary for bowtie (that you downloaded from SourceForge) into /usr/local/bin/ or any other folder in your PATH.