Display Settings:

Format

Send to:

Choose Destination
J Comput Biol. 2006 Oct;13(8):1457-64.

fjoin: simple and efficient computation of feature overlaps.

Author information

  • The Jackson Laboratory, Mouse Genome Informatics, Bar Harbor, Maine 04609, USA. jer@informatics.jax.org

Abstract

Sets of biological features with genome coordinates (e.g., genes and promoters) are a particularly common form of data in bioinformatics today. Accordingly, an increasingly important processing step involves comparing coordinates from large sets of features to find overlapping feature pairs. This paper presents fjoin, an efficient, robust, and simple algorithm for finding these pairs, and a downloadable implementation. For typical bioinformatics feature sets, fjoin requires O(n log(n)) time (O(n) if the inputs are sorted) and uses O(1) space. The reference implementation is a stand-alone Python program; it implements the basic algorithm and a number of useful extensions, which are also discussed in this paper.

PMID:
17061921
[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Write to the Help Desk