VITESSE V2.0

(c)1995
Jeff O'Connell

Table of Contents

• WHAT'S NEW
• DESCRIPTION
• RUNNING
• LIMITATIONS
• ALELLE LUMPING/RECODING
• SCREEN OUTPUT
• PEDIGREE/MENDELIAN INCONSISTENCIES
• MEMORY
• COMPARING RESULTS FROM VITESSE AND LINKAGE/FASTLINK
• GAS/VITESSE INTERFACE
• VERSION 2.0
• BETA TESTERS
• PUBLICATION CITATION

VITESSE is a software package that computes likelihoods with the functionality of the LINKMAP and MLINK programs from LINKAGE.

VITESSE uses the novel algorithms of set-recoding and fuzzy inheritance to reduce the number of genotypes needed for exact computation of the likelihood, which accelerates the calculation. It also represents multilocus genotypes locus-by-locus to reduce the memory requirements.

The algorithms in VITESSE were developed and coded by Jeff O'Connell at the University of Pittsburgh. Dan Weeks at the University of Pittsburgh and the Wellcome Trust Centre for Human Genetics at Oxford University collaborated.

Running VITESSE requires that you be familiar with running the LINKAGE/FASTLINK package. If you have not used LINKAGE/FASTLINK you can find user manuals and other very helpful information on Jurg Ott's Linkage Analysis Web Site at Columbia University.

• VITESSE is currently set up to run in an lcp-generated script file.

• I have included a program called cnvrt_sh to convert any lcp-generated shell file to another shell file for running VITESSE. Basically it strips out calls to the LINKAGE/FASTLINK programs mlink and linkmap and replaces them with calls to vitesse. For example,

   % cnvrt_sh
   Input file :pedin
   Output file: vpedin
     -> 79 lines processed
   %
  

• Set any necessary paths to where you keep the vitesse and other executables.

• The converted shell file also has some different file names. The output files are the same as for LINKAGE/FASTLINK except that the letter 'v' is appended as a prefix. For example, 'final.out' becomes 'vfinal.out'.

  The reason the output is not the same is so that the user can compare answers with LINKAGE/FASTLINK by running both shell files.

• The LINKAGE/FASTLINK program UNKNOWN is not used by VITESSE and so it is stripped from the shell file.

Version 1.0 will only handle simple pedigrees. Simple means there are no loops and there is only one set of parents who are founders. I'm actively working on general pedigrees without loops. Yes, I know this limitation is annoying!!

• If VITESSE encounters a pedigree it cannot handle it issues a message and exits. I have included yet another shell converter 'pedshell' to assist you in determining which pedigrees are simple. Use 'pedshell' to convert an lcp-generated shell file to another shell file containing a call to the program 'pedcheck'. For example,

   %pedshell 
   Input file :pedin
   Output file: ppedin
     -> 79 lines processed
   %
  

  When you run 'ppedin', a message will be displayed after each pedigree that is not simple. Delete those pedigrees from the pedigree file (make a backup first) and then run VITESSE.

  For example, if you generated 'pedin' using lcp, then convert 'pedin' to say 'ppedin' and run it. Delete pedigrees, if necessary. Then convert 'pedin' to 'vpedin' and run it.

NEVER RECODE ALLELES. VITESSE does its own allele recoding. Hand recoding may lead to errors and any 'allele lumping' will not affect VITESSE's running time. My experience is that LINKAGE/FASTLINK does not always handle more than 31 alleles at a locus correctly. VITESSE has no restrictions on the number of alleles at a locus.

SCREEN OUTPUT

The final output from VITESSE appears at the end of the run because the program is optimized for MLINK and LINKMAP runs. This means that when a trait locus moves between two markers, all thetas are done for that pedigree, instead of doing all pedigrees for one theta. VITESSE will print which pedigree is is processing.

The output during the run is much different than LINKAGE. VITESSE prints the state of the calculation to give the user an idea of the of how complex the problem is. As each nuclear family is peeled from the pedigree, VITESSE prints the id's of the parents and children, and the number of Parental Pairs. This is the number of valid multilocus genotype pairings for the parents. For each pair, a calculation involving the compatible child genotypes is done, so this number relates to the complexity of that nuclear family, and thus the pedigree - the more pairs, the longer the calculation. As you run different pedigrees or add markers, you should get a feel for the time complexity of the problems.

When you reach the last nuclear family, the output looks slightly different because VITESSE uses a novel algorithm to exploit a special symmetry in this family which can lead up to 2-fold speed up.

The time and space complexity of LINKAGE/FASTLINK is associated to the product of the number of alleles of the markers, called Maxhap. This constant is actually a false indicator of the complexity of the problem. The space and time complexity of VITESSE is a function of the number of markers and the number of parental genotypes in the pedigree. Note that Maxhap is irrelevant in VITESSE.

I'm developing a preprocessor program that will quickly give this complexity information without doing the entire likelihood calculation.

PEDIGREE/MENDELIAN INCONSISTENCIES

VITESSE assumes to some extent that the pedigree file is correct and does not have extensive diagnostic checking. Assuming the pedigree file is correct, VITESSE is guaranteed to find any Mendelian inheritance inconsistencies in your pedigree. If VITESSE finds an inconsistency it exits and gives information on the screen and in the file 'vitesse.dbg' to assist you in locating the problem.

The memory requirements are a function of the number of loci and number of parental pairs. On most problems I've reached the time complexity before the memory limit. I am testing other implementations which use less memory and have not decided yet how to or whether to separate versions.

• IMPORTANT: VITESSE ALWAYS computes the exact likelihood. In LINKAGE/FASTLINK, if you use UNKNOWN, then the likelihood may not be preserved because if everyone is untyped then they are made homozygous 1/1 with that allele frequency. (And I believe there are other things LINKAGE does unrelated to UNKNOWN that may alter the likelihood.) In general, my experience is that the more complex the pedigree, the more likely the likelihood will be preserved. Although these techniques alter the raw likelihood the LOD scores are preserved.

• IMPORTANT: The log base 10 output of LINKAGE/FASTLINK is not always accurate. That is because the programs doesn't use the log10 function, but rather divide the natural log function by a fixed- length constant. This problem may have been fixed in newer versions of Pascal LINKAGE 5.* and is fixed LINKAGE 6.0. Note that the inaccuracy is minor, becuase the answers are fine to 2-3 decimal places.

  For example, on my Sun Workstation I get inaccurate log10 answers from FASTLINK. To get better accuracy in FASTLINK change the log10_ value in commondefs.h to 2.302585093 or replace it with '(log(10.0))'.

• IMPORTANT: Since VITESSE is a new program and uses completely different algorithms than LINKAGE/FASTLINK, comparing output is advised where possible. In general, the bugs I found while developing VITESSE appeared while running 2-point analyses, so if all the 2-point runs agreed, other multipoint runs using those markers agreed.

• *THUS, TO COMPARE:
  1. CHANGE THE LOG 10 CONSTANT; OTHERWISE LODS WON'T BE ACCURATE AND WON'T MATCH WITH VITESSE.
  2. . IN THOSE CASES WHEN LINKAGE/FASTLINK GIVES EXACT LIKELIHOODS THEN VITESSE MUST GIVE THE SAME NATURAL LOG AND BASE 10 LOG VALUES. THE LOD SCORES, HOWEVER, MUST ALWAYS MATCH BETWEEN THE PROGRAMS.

GAS/VITESSE INTERFACE

VITESSE is also available with an alternative interface as part of the GAS system -- Genetic Analysis System by Alan Young, Oxford University.

The GAS/VITESSE implementation offers some different functionality than LINKMAP and MLINK, allowing 2-locus optimization of theta, exclusion mapping automated multi-point (up to 8 loci simultaneously) mapping across any number of adjacent marker loci, and produces a postscript file for direct graphical output.

For more details use either:

• WWW to http://info.ox.ac.uk/~ayoung/gas.html (here)
• FTP to ftp.ox.ac.uk directory pub/users/ayoung (here) or
• send mail to ayoung@vax.ox.ac.uk.

VITESSE is also available at the above sites.

• handles general pedigrees without loops. (Actually loops have been implemented, but due to internal data structure design the performance is not good at the moment, so that code has not been released yet. For larger pedigrees with loops I recommend FASTLINK, MENDEL or SIMWALK2 - the latter two if there are a lot of loops)
• has Ilink capability
• handles genotype specific penetrances. Specify 4 penetrances instead of 3. The order of the trait genotypes is 1|1 1|2 2|1 2|2 with paternal allele on the left. Note that the order of the heterozygotes is opposite that of ghi (genehunter imprinting version). To run imprinting add the command line option -L I.
• uses the child vector algorithm as described in the reference below. VITESSE will automatically switch between the parental pair and child vector algorithm. To run only the parental pair algorithm (original vitesse) use the command line option -1 f. To run only the child vector algorithm use the command line option -1 c.
• does NOT do the byfamily likelihoods (lods) by default as version 1 does. To obtain the byfamily results use the command line option -F.
• can print the lod scores for a LINKMAP run by using the command line option -M
• can use non-default names for pedigree and data files by using the command line options -p and -d , respectively.
• accepts phased data in the pedigree file. Genotypes in LINKAGE format are written as A B, which a priori represents 2 phases, A | B and B | A where A | B represents the genotype with A being the paternal and B the maternal allele. VITESSE accepts genotypes of the form A | B.
• accepts groups of genotypes at a locus. Enclose the group with { }. Example { 1 2 3 4 } represents two genotypes 1 2 and 3 4. Thus { A | B B | A } is the same as A B.
• accepts half-typed genotypes. If one allele is known with certainty, say the A allele, then A 0 can be entered in the pedigree file. Normally VITESSE treats this as an error. To override the error message use the command line option -Z.

Complexity:

I would like to thank the following Beta testers for excellent information and suggestions on improving VITESSE and platform compatibility.

Jim Tomlin, NIH
Venkateswara Rao Parasa, NIH

John I. Powell, NIH

Alan Young, Oxford University

PUBLICATION CITATION

"The VITESSE algorithm for rapid exact multilocus linkage analysis via genotype set-recoding and fuzzy inheritance",
O'Connell JR, Weeks DE, Nature Genetics 11:402-408, December 1995

O'Connell JR (2001) Rapid Multipoint Linkage Analysis via Inheritance Vectors in the Elston-Stewart Algorithm. Hum Hered. 51(4):226-40.

Please reference this if you use VITESSE in any published work.

I'm very interested in receiving feedback on your experiences. If you have any questions, problems, suggestions, or comments, please get in touch.

Thank you for your assistance,

Jeff O'Connell