liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
FAAST: Flow-space Assisted Alignment Search Tool
Linköping University, Department of Physics, Chemistry and Biology, Bioinformatics . Linköping University, The Institute of Technology.
Karolinska Institute.
Linköping University, Department of Physics, Chemistry and Biology, Bioinformatics . Linköping University, The Institute of Technology.
2011 (English)In: BMC Bioinformatics, ISSN 1471-2105, Vol. 12, no 293Article in journal (Refereed) Published
Abstract [en]

Background: High throughput pyrosequencing (454 sequencing) is the major sequencing platform for producing long read high throughput data. While most other sequencing techniques produce reading errors mainly comparable with substitutions, pyrosequencing produce errors mainly comparable with gaps. These errors are less efficiently detected by most conventional alignment programs and may produce inaccurate alignments. less thanbrgreater than less thanbrgreater thanResults: We suggest a novel algorithm for calculating the optimal local alignment which utilises flowpeak information in order to improve alignment accuracy. Flowpeak information can be retained from a 454 sequencing run through interpretation of the binary SFF-file format. This novel algorithm has been implemented in a program named FAAST (Flow-space Assisted Alignment Search Tool). less thanbrgreater than less thanbrgreater thanConclusions: We present and discuss the results of simulations that show that FAAST, through the use of the novel algorithm, can gain several percentage points of accuracy compared to Smith-Waterman-Gotoh alignments, depending on the 454 data quality. Furthermore, through an efficient multi-thread aware implementation, FAAST is able to perform these high quality alignments at high speed. The tool is available at

Place, publisher, year, edition, pages
BioMed Central , 2011. Vol. 12, no 293
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-70511DOI: 10.1186/1471-2105-12-293ISI: 000294177700001OAI: diva2:440121
Funding Agencies|Swedish Research Council, the Research School of Medical Bioinformatics||Available from: 2011-09-12 Created: 2011-09-12 Last updated: 2012-12-10
In thesis
1. Bioinformatic methods for characterization of viral pathogens in metagenomic samples
Open this publication in new window or tab >>Bioinformatic methods for characterization of viral pathogens in metagenomic samples
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Virus infections impose a huge disease burden on humanity and new viruses are continuously found. As most studies of viral disease are limited to theinvestigation of known viruses, it is important to characterize all circulating viruses. Thus, a broad and unselective exploration of the virus flora would be the most productive development of modern virology. Fueled by the reduction in sequencing costs and the unbiased nature of shotgun sequencing, viral metagenomics has rapidly become the strategy of choice for this exploration.

This thesis mainly focuses on improving key methods used in viral metagenomics as well as the complete viral characterization of two sets of samples using these methods. The major methods developed are an efficient automated analysis pipeline for metagenomics data and two novel, more accurate, alignment algorithms for 454 sequencing data. The automated pipeline facilitates rapid, complete and effortless analysis of metagenomics samples, which in turn enables detection of potential pathogens, for instance in patient samples. The two new alignment algorithms developed cover comparisons both against nucleotide and  protein databases, while retaining the underlying 454 data representation. Furthermore, a simulator for 454 data was developed in order to evaluate these methods. This simulator is currently the fastest and most complete simulator of 454 data, which enables further development of algorithms and methods. Finally, we have successfully used these methods to fully characterize a multitude of samples, including samples collected from children suffering from severe lower respiratory tract infections as well as patients diagnosed with chronic fatigue syndrome, both of which presented in this thesis. In these studies, a complete viral characterization has revealed the presence of both expected and unexpected viral pathogens as well as many potential novel viruses.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. 65 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1489
National Category
Natural Sciences
urn:nbn:se:liu:diva-86194 (URN)978-91-7519-745-6 (ISBN)
Public defence
2013-01-25, Planck, Fysikhuset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Available from: 2012-12-10 Created: 2012-12-10 Last updated: 2012-12-10Bibliographically approved

Open Access in DiVA

fulltext(877 kB)131 downloads
File information
File name FULLTEXT01.pdfFile size 877 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lysholm, FredrikPersson, Bengt
By organisation
Bioinformatics The Institute of Technology
In the same journal
BMC Bioinformatics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 131 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 125 hits
ReferencesLink to record
Permanent link

Direct link