It gives us great pleasure to present the proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI 2004) which took place in Bergen, Norway, September 17-21, 2004. The WABI 2004 workshop was part of a ?- conference meeting, which in addition to WABI, included ESA, WAOA, IWPEC, and ATMOS, hosted by the University of Bergen, Norway. See http: //www.ii.uib.no/algo2004/ for more details. TheWorkshoponAlgorithmsinBioinformaticscoversresearchonallaspects of algorithmic work in bioinformatics. The emphasis is on discrete algorithms that address important problems in molecular biology. These are founded on sound models, are computationally e'cient, and have been implemented and tested in simulations and on real datasets. The goal is to present recent research results, including sign'cant work in progress, and to identify and explore dir- tions of future research. Original research papers (including signi'cant work in progress) or sta- of-the-art surveys were solicited on all aspects of algorithms in bioinformatics, including, but not limited to: exact and approximate algorithms for genomics, genetics, sequence analysis, gene and signal recognition, alignment, molecular evolution, phylogenetics, structure determination or prediction, gene expression and gene networks, proteomics, functional genomics, and drug design. We received 117 submissions in response to our call for papers, and were able to accept 39 of these. In addition, WABI hosted one invited distinguished lecture, given to the entire ALGO 2004 conference, by Dr. Marie France Sagot of the INRIA Rhon DEGREES e-Alpes laboratories in France.