Update May 2021
Find relatives (autosomal & X-DNA)
Statistically everyone inherits at least a DNA piece from every great-great-grandparent (4th generation, 16 ancestors). Beginning with the 5th generation the genetic ancestors diminish: 8th generation 220/256 ancestors, 16th generation 1018/65536 ancestors (Source).
This means usually it is possible to find all 2nd cousins trough widespread autosomal DNA testing; most of 3th to 4th cousins, some of 5th to 6th cousins and in exceptional cases even further (Link).
If your goal is finding relatives by entering the biggest autosomal/X-DNA database for matching the suggestion is to Direct to Consumer (DTC) SNP chip test with:
AncestryDNA @ Ancestry.com ($99 US, €69+10 DE/AT, + 31 countries/no IT/CH). The second option is 23andMe ($99 US + IT/DE/AT/CH + 49 countries). Third option is FamilyTreeDNA FamilyFinder ($79+10 IT/DE/AT/CH) or MyHeritage (€79 IT/DE/AT/CH).
According to ISOGG Autosomal DNA testing comparison chart the number of at/X SNPs tested do not differ much: Ancestry 637k, 23andMe 630k, FTDNA 612k, MyHeritage 575k. Higher numbers of SNPs and overlapping with the other companies facilitate comparison and matching accuracy.
As soon as you have results, download raw-data and for additional matches consider uploading to:
FamilyTreeDNA (start free), MyHeritage DNA Upload for Free, GEDmatch (basic free). Possibly interesting to upload: BorlandGenetics, DNA.Land, Geneanet. Unfortunately the at/X-DNA chip tests do not test for the same SNPs (Genome positions) so comparison between companies become less accurate caused by down to only 23% shared SNPs of the ca. 600k (MyHeritage and possibly LivingDNA are the top performers).
Patrilineal Y-DNA (matching for males)
If no known male cousin of the same surname/clan has tested yet at FamilyTreeDNA with the biggest DTC Y-STR database, do so by ordering the Y-37 STR-Marker test ($119) to see if you have matches. You can join Projects and order upgrades. Big Y 700 ($449) is their most comprehensive Y-Test.
Experts might consider the alternative YSEQ STR Alpha-Beta 37 Marker Panel ($85) and doing a WGS. Trough accurate Y-pedigrees this allows to reconstruct paternal line relationships and make migration hypotheses.
Modern advanced Whole Genome Sequencing (WGS)
If you have an expert to support you a WGS 15x, 30x or better is the future to get the most comprehensive data for Y-, mt- and autosomal/X-DNA. Unfortunately no company with a big matching database of Y/mt/at/X-DNA included in the service does provide an interesting WGS test. So you need to go with those providing the WGS raw data and analysis results (ancestry/haplogroups, health):
YSEQ is suggested as they provide the Y, mt and autosomal/X files needed for Genetic Genealogy. Since 2021 they offer WGS 15×400 $399 or the WGS 30×400 for double the price.
The following DTC-Providers while offering cheap sales suffer with less QC (Quality Control) and long pending time:
Dante Labs WGS 30x (€499, with sales 299 and lower) seems to not offer tests in all Western Countries anymore
Nebula Genomics WGS 30x $299 + Nebula Explore $10/month Subscription
Y-Upload/Services for WGS: YFull ($49 incl. mt), ydna-warehouse (free), mitoYDNA;
mt-Upload/Services: YFull ($25), mitoYDNA;
Autosomal/X-Upload/Services: various conversion tools like useGalaxy, WGSExtract (Manual), samtools/Linux or services like YSEQ FASTQ Mapping $25; Links: ISOGG Raw DNA data tools & Autosomal DNA tools, Genetic Analysis Tools; suggested upload to services listed above under “find relatives”.
Hair and other Human Specimens and Remains
Human hair testing without part of the follicle and only from the hair shaft seems to be near to impossible because the outer hair is build by Keratin and contains no nuclear DNA (only mtDNA). So the hair root needs to be present and the test is still complex and mostly only forensic labs have experience with it (laboratoryinfo 2021). For 6 or more strands with the intact hair follicles (roots) a Hair DNA Test in USA is available for $650 with an extraction success rate of ca. 85%. The same US-company offers also testing for other DNA Specimens like from Blood Stains, Envelope Flaps, Ear Swap, Teeth, Fingernails, Mucus, etc. for the same cost.
Blood Cards: Family Tree DNA accepts them with a $250 fee for each DNA extraction with no success guarantee.