GERMLINE

About

GERMLINE is an algorithm for discovering long shared segments of Identity by Descent (IBD) between pairs of individuals in a large population. It takes as input genotype or haplotype marker data for individuals (as well as an optional known pedigree) and generates a list of all pairwise segmental sharing.

GERMLINE uses a novel hashing & extension algorithm which allows for segment identification in haplotype data in time proportional to the number of individuals. Presently, GERMLINE can execute on phased or un-phased data; though we have found performance much improved with phasing while phasing & running GERMLINE is still significantly faster than comparable IBD algorithms. Utilities for easily phasing data for GERMLINE are available below. GERMLINE can identify shared segments of any specified length, as well as allow for any number of mismatching markers.

The program has been developed in Itsik Pe'er's Lab of Computational Genetics at Columbia University. It has been built in C++ and tested in the Red Hat Linux environment; the source is available here in a tar.gz package as well as pre-compiled binaries under the utilities section. GERMLINE is distributed under the GPL license. If you use GERMLINE in a published analysis, please cite Gusev A, Lowe JK, Stoffel M, Daly MJ, Altshuler D, Breslow JL, Friedman JM, Pe'er I (2008) Whole population, genomewide mapping of hidden relatedness. Genome Research.

This work has recently been applied to optimally selecting individuals for sequencing and inferring previously un-typed variants in Low-pass Genomewide Sequencing and Variant Imputation Using Identity-by-descent in an Isolated Human Population. (2011) A Gusev, MJ Shah, EE Kenny, A Ramachandran, JK Lowe, J Salit, CC Lee, EC Levandowsky, TN Weaver, QC Doan, HE Peckham, SF McLaughlin, MR Lyons, VN Sheth, M Stoffel, FM De La Vega, JM Friedman, JL Breslow, I Pe'er (in submission, pre-pub version).

download: germline 1.5.1 (03.07.12)

Usage

From the command line, extract germline with tar xzvf germline-X-X-X.zip, enter the extracted directory, and compile germline with make all. A simple test-case using shortened HapMap samples can be run using make test. The executable is run as germline <options> which prompts the user for input/output file information and runs the algorithm.

Input

GERMLINE accepts as input the following formats:

NOTE: Although the PLINK format is not intended for haplotypes, GERMLINE expects the respective alleles to appear in order; i.e. the first allele always corresponds to one haplotype and the second allele to the other. Also, PLINK arbitrarily re-orders the alleles in processing the files, so we do not recommend handling phased data with PLINK prior to GERMLINE analysis because the haplotypes may not be intact (use the -from_snp and -to_snp flags to target specific regions).

Output

Upon completion, GERMLINE generates a .match and .log file in the specified location. Each line in the .match file corresponds to a pairwise shared segment, with the following fields:

Binary Output

To spave space GERMLINE can also generate binary output using the -bin_out flag. This flag will generate three files:

The binary files can be converted back to the standard flat format described above by using the parse_bmatch utility provided with the code. Load the three generated files using parse_bmatch [BMATCH FILE] [BSID FILE] [BMID FILE] and the flat match output will be printed to standard out. See the parse_bmatch.cpp code for binary format details.

Options

The program has several command line options to direct the segmental sharing process:

FlagDefaultDescription
-map-File location for genetic distance map. Uses the PLINK map format.
-min_m3Minimum length for match to be used for imputation (in cM or MB).
-err_hom2The maximum number of mismatching homozygous markers for a slice to still be considered part of a match.
-err_het0The maximum number of mismatching heterozygous markers for a slice to still be considered part of a match.
-from_snp-Indicate the ID of the first SNP to start processing from.
-to_snp-Indicate the ID of the last SNP to end processing with.
-h_extendExtends from exact seeds using haplotypes rather than genotypes; useful when data is well-phased (e.g. trios)
-homozAllow self matches (runs of homozygosity)
-homoz-onlyAnalyze and report only auto/homo-zygous segments, no IBD reported but significantly faster analysis.
-haploidTreat each input individual as two distinct and separate haplotypes. Output IDs will have .0/.1 suffix corresponding to each haplotype. The -err_het flag will have no effect in this analysis.
-bin_outGenerate output matches in binary format, creates a *.bmatch *.bsid and *.bmid files. These files can be converted to flat output using the parse_bmatch utility included and compiled in the package.
-bits128Size of each slice (in markers) used for exact matching seeds.
-w_extendExtend the match beyond the slice end to the first mismatching marker.

Utilities

We have created some script utilities for converting between data formats; the source code is available below. All scripts can be compiled using g++ [script file] -o [output name].

TitleUsageDownload
Phasing Pipeline Pipeline for phasing PLINK format data with BEAGLE and processing in GERMLINE. README for detailed usage. phasing_pipeline.tar.gz
Binaries Pre-compiled binaries of GERMLINE v1.5.0 for Linux 32/64 bit and Windows (cygwin). 32b, 64b, WIN

Contact

For any questions or comments, please the developers directly at: {gusev,itsik}@cs.columbia.edu.

Change Log

1.5.1 (03.07.12)
Fixed minor formatting bug with runs of homozygosity

1.5.0 (09.17.10)
Major computational overhaul - algorithm should run 2-3 times faster with 4-fold memory reduction on large datasets.
Added a binary output option (flag -bin_out) to reduce output size, see documentation.
Added a stand-alone C++ script to convert from binary file to standard readable match file.
Added -haploid flag to treat each input individual as two distinct haplotypes, output IDs will have .0/.1 suffix indicating which respective haplotype the match is on. This is effective for short windows with very well phased data.

1.4.2 (07.22.10)
Fixed bug with -to_snp/-from_snp commands
Added -homoz-only flag for simple homozygosity analysis

1.4.1 (03.22.10)
Fixed bug in PHASE format input
Fixed bug in files with multiple chromosomes
Fixed bug with overlapping segments from -h_extend feature

1.4.0 (08.14.09)
Allows self-matches between individuals (include -homoz flat)
Added columns to indicate weather match is homozygous or heterozygous

1.3.0 (12.22.08)
Now handles unphased data (omit -h_extend flag).
Added options for homozygous / heterozygous in-exact matching.
Output now specifies if match is in cM or MB.

1.2.1 (09.17.08)
Now using the boost dynamic_bitset libraries. These are packaged with the source and do not effect installation/dependency.
Added -bits flag to explicitly define word-length.
Included sample input data & test-case called upon compilation by 'make test_case'.

1.2.0 (09.03.08)
Output format has changed to provide more detailed SNP information (see above).
Can now iteratively process multi-chromosomal data (for PLINK / PED format only).
Genotype calling has been removed for the time being.
Genetic map restructured (see above) and processed as a parameter.

1.0.2 (08.12.08)
Updated the HapMap format input - auto-detection of trio or unrelated input.

1.0.1 (06.09.08)
Added options to perform analysis on specific region (see -from_snp, -to_snp flags).
Added option to print haplotypes and matches (see: -haps, -print flags).