BACKGROUND
the modelling of human genetic variation is critical to the understanding of the genetic basis for complex diseases.
single nucleotide polymorphisms  are the most frequent form of variation.
the human genome project and other large-scale efforts have identified millions of snp markers.
although each marker can be analyzed independently, it is more informative to analyze them in groups.
therefore, it is useful to analyze haplotypes , which are sequences of linked markers on a single chromosome.
in diploid organisms, such as human beings, chromosomes come in pairs, and experiments often yield genotype information, which blend haplotype information for chromosome pairs.
there is growing evidence that, in order to better characterize the role of a candidate gene, full haplotype information should be exploited instead of using only genotype information.
unfortunately, it is both time-consuming and expensive to derive haplotype information experimentally.
this explains the increasing interest in inferring haplotype information, or haplotyping, computationally.
in fact, the potential use of haplotypes has led to the initiation of the hapmap project which is to investigate haplotype patterns in the human genome in different populations.
haplotype inference and frequency estimation are essential components of this endeavour.
genotype data can be with or without any pedigree information, the first category is called population genotype data while the second one is pedigree genotype data.
a large number of algorithms have been designed to estimate haplotype frequencies based on population data  <cit> .
among them, em algorithms are most popular due to their interpretability and stability.
for any given pedigree genotype data, we can certainly discard the pedigree information and simply take the genotype sequences as the input of em estimation algorithms for population data.
however, it is well accepted that information obtained by analyzing pedigree genotype data is more reliable: the constraint provided by other members in a pedigree would force one genotype to settle on a unique haplotype pair as being most probable.
here we propose a two-stage method to estimate haplotype frequencies in pedigrees.
the first stage is the haplotyping stage, which finds out all feasible haplotype configurations for each pedigree.
in the second estimation stage, we use em algorithm to estimate haplotype frequencies in pedigrees based on the haplotype configurations inferred in the former stage.
in general, haplotyping pedigrees need consider the entire solution space of all possible consistent haplotype configurations.
however, the genomic dna can be partitioned into long blocks such that recombinations within each block are rare or even nonexistent  <cit> .
thus it is believed that haplotype configurations with fewer recombinations should be preferred in haplotype inference  <cit> .
when the region of interest is so small that the expected number of recombinations in the pedigree data is very close to zero, the solution space of all consistent haplotype configurations can be replaced by that of zero recombination  to estimate haplotype frequencies.
it is because the contribution of the solutions of recombinations to the overall likelihood becomes so small compared to those of zero recombination while they bring considerable complexity to the computation.
thus, we are interested in finding the consistent haplotype configurations of zero recombination.
wijsman  <cit>  proposed a 20-rule algorithm, and o'connell  <cit>  described a genotype-elimination algorithm, both of which can be used to find out zero-recombinant haplotype configurations for pedigrees.
recently, li and jiang  <cit>  showed that it could be solved in polynomial time.
here we propose an algorithm to find out zero-recombinant haplotype configurations in linear time using a technique called hcl-linkage analysis.
in the second stage, we use the em algorithm to estimate haplotype frequencies based on haplotype configurations obtained from the haplotyping stage.
we employ the hardy-weinberg equilibrium to obtain the probabilities of founder genotypes and use a genetic model  <cit>  to deduce the transmitted probabilities of non-founders.
while the likelihood of each configuration is computed by multiplying the probabilities of each genotype, the frequency of each haplotype that appears in the configuration is calculated by a gene-counting method.
we implement all the algorithms in a c software package named hanap  and test its effectiveness and efficiency both on simulated and real data sets.
the experimental results show that, our method runs much faster than the direct frequency estimation software that discards the pedigree information.
moreover, because our method utilizes such information, the estimation is more reliable.
methods
haplotyping stage: haplotyping algorithm based on hcl-linkage analysis
excoffier's em algorithm was widely applied in haplotype analysis  <cit> .
unfortunately, it should calculate the frequencies of all possible haplotype pairs consistent to each given genotype, which is unbearable in storage when the haplotype length grows to more than  <dig>  <cit> .
o'connell  <cit>  showed that genetic information from relatives could be used to resolve one genotype's ambiguity, and thus reduce the number of haplotypes that should be considered.
however, o'connell's method had an exponential time complexity.
recently, li and jiang  <cit>  showed that, for any genotype in a given pedigree, its ambiguity could be solved in cubic time ), where n is the number of members in the pedigree and m is the number of loci in each genotype.
here we present a so-called hcl-linkage analysis method to do haplotyping in linear time ).
hcl-linkage definition
trios are simple pedigrees that contain only a pair of parents and a child.
a consistent zero-recombinant haplotype configuration for a general pedigree should also be a consistent zero-recombinant haplotype configuration when restricted to each trio in this pedigree.
given trio t = , here f is the father, m is the mother and c is the child, suppose that locus i of f, m, and c have alleles {a, b}, {c, d} and {e, f} ).
the genotype information of c can be homozygous or heterozygous.
if it is homozygous , then it is clear that the paternal allele and the maternal allele are the same .
the situation becomes complicated if it is a heterozygous site .
table  <dig> lists out all possible situations.
we can see that given the locus genotype information for the three members, it may or may not be possible to determine the paternal allele and the maternal allele for the child.
we call a locus ambiguous if its inheritance relationship cannot be resolved.
in fact, for any trio, ignoring the ambiguous loci, the consistent  haplotype configuration for the unambiguous loci is unique and specifies a linkage of alleles on some heterozygous loci for each node in the trio.
we define such linkage as hcl-linkages .
definition
an hcl-linkage ψ is a quadruplet <v, re, ls, ph>defined on node v and specified by the unique consistent  haplotype configuration within a trio that contains v. here v denotes the node to which the hcl-linkage belongs.
ls = {a <dig> ...,al} is the set of heterozygous loci where the haplotype configuration has been inferred.
ph = {ph, ph'} = {, } records the two  haplotypes imputed on these loci.
re =  denotes that ph  is inherited from or will be passed on to the node in set r.
an hcl-linkage describes the partial haplotype configuration of a node and the inheritance relationship between the parents and their children.
under our definition, we can conclude that every haplotype configuration should be consistent with any hcl-linkage specified by each trio in the pedigree.
merge and transfer operations over hcl-linkages
in the case of multiple generations and multiple children, loci on one node may be linked by different hcl-linkages.
hcl-linkages of the same node should be merged if they can.
there are three cases when merging two hcl-linkages ψ <dig> = <v, , ls <dig>  {ph <dig>  ph1'}> and ψ <dig> = <v, , ls <dig>  {ph <dig>  ph2'}> on node v.
case :  ∩  ≠ Φ
l.a) r <dig> ∩ r <dig> ≠ Φ or r1' ∩ r2' ≠ Φ, it means that both ph <dig> and ph <dig> are from the nodes in r <dig> and r <dig> said ph1' and ph2' are from the nodes in r1' and r2', so ph <dig> and ph <dig> should be on the same haplotype, and ph1' and ph2' on the other: i) ls <dig> ∩ ls <dig> = Φ, or ls <dig> ∩ ls <dig> ≠ Φ but ph <dig> equals ph <dig> when restricted to loci in ls <dig> ∩ ls <dig>  it means that ψ <dig> and ψ <dig> are compatible.
in this case, they should be merged to ψ = <v, , ls <dig> ∪ ls <dig>  {ph <dig> ∪ ph <dig>  ph1' ∪ ph2'}>, here ph <dig> ∪ ph <dig> denote a longer partial haplotype, which alleles equal to those of ph <dig> and ph <dig> when restricted to loci in ls <dig> and ls2; ii) ls <dig> ∩ ls <dig> ≠ Φ and ph <dig> doesn't equal ph <dig> when restricted to ls <dig> ∩ ls <dig>  it means that ψ <dig> and ψ <dig> are incompatible, i.e.
no haplotype configuration can satisfy the two hcl-linkages in the same time.
<dig> b) r <dig> ∩ r2' ≠ Φ or r1' ∩ r <dig> ≠ Φ, it means that ph <dig> and ph2' should be on the same haplotype, and ph1' and ph <dig> on the other.
similarly, ψ <dig> and ψ <dig> can be merged to ψ = <v, , ls <dig> ∪ ls <dig>  {ph <dig> ∪ ph2', ph1' ∪ ph2}> when they are compatible.
case :  ∩  = Φ, but ls <dig> ∩ ls <dig> ≠ Φ,
<dig> a) ph <dig> equals ph <dig>  or ph <dig> equals ph2'  when restricted to ls <dig> ∩ ls <dig>  it means that ψ <dig> and ψ <dig> are compatible, in this case, they should be merged to ψ = <v, , ls <dig> ∪ ls <dig>  {ph <dig> ∪ ph <dig>  ph1' ∪ ph2'}> or ψ = <v, , ls <dig> ∪ ls <dig>  {ph <dig> ∪ ph2', ph1' ∪ ph2}>.
<dig> b) else, ph <dig> doesn't equal ph <dig> or ph2' when restricted to ls <dig> ∩ ls <dig>  it means that ψ <dig> and ψ <dig> are incompatible.
case :  ∩  = Φ, and ls <dig> ∩ ls <dig> = Φ,
in this case, ψ <dig> and ψ <dig> cannot be merged and both should be recorded in a hcl-linkage set Ψv for node v.
with the merge operation, we can define the normalizing of a set of hcl-linkages Ψv: normalizing a set Ψv of hcl-linkages on node v means repeatedly applying the merge operation for pairs of hcl-linkages in Ψv until, ∀ψi, ψj ∈ Ψv,  ∩  = Φ, and ls <dig> ∩ ls <dig> = Φ. Ψv is then said to be normalized.
from now on, if there is no further notice, Ψv should be normalized after any changes.
like genetic information, hcl-linkages will be passed on from generations to generations.
without loss of generality, let us define the transfer of hcl-linkage information from child c to its parent f. the other case from f to c would be similar.
let Ψc and Ψf represent the normalized hcl-linkage sets of c and f respectively, and let hs be the set of homozygous loci of f. the transfer of Ψc from c to f results in changes to Ψf, where each ψc = <c, , lsc, {phc, phc'}> ∈ Ψc is transferred independently.
there are two cases to consider.
case : if f ∈ rc , add ψf = <f, , lsc - hs, {phf, phf'}> to Ψf, here phf equals the resulting partial haplotypes of phc  when restricted to loci in lsc - hs and phf' is the compensatory partial haplotypes of phf consistent to genotype gf.
case : else, f ∉ rc ∪ rc': i) both phc and phc' are consistent with the partial genotype gf when restricted to loci in lsc, then add ψf = <f, , lsc - hs, {phf, phf'}> to Ψf, here phf and phf' equal the resulting partial haplotypes of phc and phc' when restricted to loci in lsc - hs; ii) phc'  is not consistent with the partial genotype gf when restricted to loci in lsc, then add ψf = <f, , lsc - hs, {phf, phf'}> to Ψf, here phf equals the resulting partial haplotypes of phc  when restricted to loci in lsc - hs and phf' is the compensatory partial haplotypes of phf consistent to genotype gf.
note that at least one of phc and phc' should be consistent with the partial genotype gf.
remember that Ψf should be normalized whenever adding a new hcl-linkage to it.
in the case of transferring an hcl-linkage ψf from f to c, resulting in adding ψc = <c, , lsc, {phc, phc'}> to Ψc, note that we should add m into rc' whenever we have determined that f ∈ rc.
our merge and transfer operations will not bring more or lose any hcl-linkage information for building consistent haplotype configurations.
main hcl-linkages analysis haplotyping algorithm
before the algorithm, we preprocess each trio in the pedigree.
whenever a trio specifies an hcl-linkage for node v, it will be stored in the hcl-linkage set Ψv.
the objective of the algorithm is to collect the complete hcl-linkage information for each node, which is accomplished by traversing the tree twice.
firstly, we will convert the input pedigree into a rooted searching tree t  .
then we traverse t in post-order to transfer and merge the hcl-linkage information for each node from its relatives .
we do this from the left lowest nuclear family fo.
the hcl-linkages in nuclear family fo will be merged at both parents, and then be transferred to the root of the sub-tree.
the same operations will be conducted in its parental nuclear family on hcl-linkages specified in this family as well as on those transferred from its child families.
and at last, we collect all the hcl-linkages at the root r. in step  <dig>  we traverse t again in pre-order and transfer the linkage in another direction from r to its farmost descendants.
after step  <dig>  the hcl-linkage set of each node preserves all hcl-linkages in the pedigree.
in step  <dig>  we choose a node v arbitrarily.
set Ψv contains several hcl-linkages ψ <dig>  ψ <dig> ...,ψl defined on disjoint locus set ls <dig>  ls <dig> ...lsl.
when a set of loci are linked by one hcl-linkage, they can be viewed as a compound locus, and the two partial haplotypes can be viewed as two compound alleles.
these "loci"  will be treated equally as the other heterozygous loci and homozygous loci that are not involved in any hcl-linkage.
we arbitrarily select one allele from the two at each locus to form a haplotype; the other alleles form another haplotype.
it is called an imputing schema.
whenever the haplotype configuration of one node is determined, it can be used to determine the configurations of its relatives, and those of the whole pedigree at last.
during our algorithm, incompatibleness may occur when normalizing hcl-linkage set Ψv.
then we declare that there is no solution and exit from the algorithm immediately.
even in step  <dig>  incompatibleness may still occur when applying the haplotypes of the parents to resolve the genotype of the children in the case that an individual node has multiple children.
figure  <dig> shows an example.
the key point is, if it exists a consistent haplotype configuration for a nuclear family , every arbitrary imputing schema s can output one feasible solution ζ. contrarily, if one imputing schema ends with incompatibleness, other schemata will fail too.
we will prove this in the appendix.
the time complexity and space complexity of our algorithm are both o where n is the number of the members in the pedigree and m is the length of the loci.
frequency estimation stage
suppose that we are given k pedigrees p = {p <dig>  p <dig> ...,pk}.
each pi consists of ni nodes vi,j , in which the first ni' are founders.
the genotype of node vi,j  is gi,j.
suppose that there are πi consistent solutions for pedigree pi and the s-th solution is: ss,i = <ss,i, <dig>  ss,i, <dig> ...,> , where ss,i,j = <αs,i,j, <dig>  βs,i,j,2> is a haplotype pair of genotype gi,j.
all haplotypes appear in these solutions form a list of haplotypes h = {h <dig>  h <dig> ...,hl} with frequencies Θ = {θ <dig>  θ <dig> ...,θl}, here θ <dig> + θ <dig> + ... + θt =  <dig> is what we want to estimate.
the likelihood of haplotype frequencies given the observed pedigree data is,
under the assumption of random mating, the paternal haplotype configuration and the maternal haplotype configuration are independent, and the child's haplotype configuration is transmitted from its parents.
we have:
here pr  is the probability of haplotype configuration of the founder nodes, it can be computed using the hardy-weinberg equilibrium.
pr is the gamete transmission probabilities of haplotype configuration ss,i,j with the parental haplotype configurations of  and .
it can be computed using a genetic model presented by elston and stewart  <cit> .
em algorithm estimates the haplotype frequencies Θ starting with the initial arbitrary values Θ = {θ <dig>  θ <dig> ...,θl}.
these initial values are used as if they were the unknown true frequencies to estimate solution frequencies pr .
these expected solution frequencies are used in turn to estimate haplotype frequencies at the next iteration Θ = {θi, θ <dig> ...,θ} , and so on, until convergence is reached.
suppose that in the r-th iteration, Θ = Θ and we want to estimate Θ. then we have:
let δi,j,t be an indicator variable equalling the number of haplotype ht appear in solution ss,i.
then the haplotype frequencies can be computed using a gene-counting method,
there are several ways to initialize the haplotype frequencies Θ = {θ <dig>  θ <dig> ...,θl}.
for instance, the initial haplotype frequencies can be chosen at random, or all haplotypes are equally frequent, i.e.
Θt = 1/l .
or that all initial haplotype frequencies are equal to the product of the corresponding single-locus allele frequencies .
also, we can set all feasible solutions for each pedigree to be equally likely, i.e.
pr) = 1/πi, .
we can even initialize the haplotype frequencies by counting their occurrence in all the feasible solutions.
since in practical applications the em algorithm could be trapped in some local maximum, we recommend to restart the algorithm several times with different initial haplotype frequencies and better with a randomized additive perturbation.
the stopping  criterion is defined as the absolute value of the difference of Θ between consecutive iterations being less than some small value ε >  <dig>
RESULTS
simulated data set
in order to generate a pedigree genotype data set for simulation experiments, we generate a population of haplotypes h* first, where each locus of each haplotype is set to some allele according to the probability distribution function p. in our simulation, we generated haplotypes of snp loci as well as haplotypes of micro-satellite loci.
for a biallelic snp locus i, suppose that i happens to be one state with a probability of pi, and to be the other state with a probability of .
for a micro-satellite loci, suppose it has w different alleles: a <dig>  a <dig> ...,aw, each appears with the probability of p <dig>  p <dig> ...,pw .
each founder node in any tested pedigree is arbitrarily assigned a pair of haplotypes according to their frequencies θ*.
the two haplotypes of a non-founder node are arbitrarily selected from those of its parents .
at last, the pair of haplotypes of the same node is blended to form a genotype corresponding to that node.
all experiments are conducted on a windows server with  <dig> g hz cpu and  <dig> mb ram.
and for each parameter setting,  <dig> copies are randomly generated and the performance is evaluated by computing the average numbers in these  <dig> runs.
running time of the haplotyping algorithm
one of the main contributions of our paper is to do haplotyping in linear time, so we firstly examine the running time with respect to different number of nodes of each pedigree  and different number of loci in each sequence .
several different tree pedigree structures are used in the simulation, the first pedigree is figure  <dig> in  <cit> , which is a tree with  <dig> nodes.
the second one is figure  <dig> in  <cit> , which is a tree with  <dig> nodes.
the third one is a  <dig> node pedigree from figure  <dig> of  <cit> .
the results are given in figure  <dig>  it is obvious that our hcl-analysis haplotyping algorithm runs in linear time and thus could be applied to large-scale haplotype analysis.
number of solutions
we compare the numbers of haplotypes that should be considered in the estimation stage, with and without the haplotyping stage.
in our experiment, we set p <dig>  and p <dig>  for snp loci, and set w =  <dig>  p <dig>  and p <dig>  for micro-satellite loci.
we let |h*| =  <dig>  and θ1* =  <dig> , θ2* = θ3* = θ4* =  <dig> , θ5* = θ6* = θ7* = θ8* =  <dig> , θ9* = θ10* = ... = θ20* =  <dig> .
when only trio pedigrees are considered, the average numbers of haplotypes are recorded in table  <dig>  we can see from the table that the numbers of haplotypes that should be estimated have been greatly reduced after the haplotyping stage , which will immediately bring the improvement on the running time.
we also consider a more complex pedigree that contains  <dig> nodes .
the average numbers of haplotypes are recorded in table  <dig>  we find that the number of haplotypes that should be estimated is even much smaller.
we also notice that the number of haplotypes is growing with the length of haplotypes and the number of pedigrees.
however, it grows very slowly.
running time of hanap
em-decoder is a popular software using the em algorithm to estimate the haplotype frequencies based on population data.
as we have pointed out, it can be used to estimate haplotype frequencies in pedigrees, simply by discarding the pedigree information.
here we also compare the running times of hanap and em-decoder.
accuracy rate of hanap
we define a parameter Δ to incarnate the deviation of the estimate haplotype frequencies from the underlying ones.
because the simulation data are generated according to the Θ*, we recognize that as the underlying true frequencies.
suppose the estimate haplotype set is he with frequencies Θe.
compare he with h*.
suppose the estimate frequencies of the  <dig> haplotypes in h* are θ1e, θ2e,...,θ20e.
we let,
two real data sets
we also test the efficiency and accuracy of hanap on two real data sets.
the first real data set is from dbmhc|abdr, a set of  <dig> trios.
each genotype of these trios contains  <dig> markers of the same position on chromosome  <dig>   <dig> of which are micro-satellite markers and others are snps.
we run hanap to find the most frequent haplotypes .
a list of  <dig> haplotypes is found by hanap.
their frequencies are shown in table  <dig>  it only takes hanap  <dig>  second to find these haplotypes while it is out of the capability of em-decoder.
the second data set is from the ceph database  <cit> , which contains  <dig> families; each consists of only three generations, usually with four grandparents, two parents and a number of children.
figure  <dig> in  <cit>  shows a typical family with  <dig> nodes.
a great portion of the alleles in this data set have not been identified, and will be viewed as missing data.
we carefully selected a data set of  <dig> families  on a block  from chromosome  <dig>  with no recombination.
both hanap and phase  are applied to this data set.
hanap inferred  <dig> haplotypes with frequency larger than  <dig>  and phase inferred  <dig> ones, among which  <dig> are common.
although we are not sure which output is closer to the real cases, the running time of hanap  is extremely shorter than that of phase .
discussion
complexities of the hcl-linkage analysis haplotyping algorithm
we show that the algorithm runs in o time and o space.
the pre-process need calculate no more than 3n hcl-linkages in no more than n trios.
each hcl-linkage can be computed in o time, so the pre-process can be done in o time.
it takes step  <dig> o time to construct the rooted tree.
in step  <dig> and step  <dig>  we have to traverse the whole tree, and visit each node for no more than constant times.
when we process the hcl-linkages from the left lowest nuclear family, we should merge the d <dig> hcl-linkages at each parent node , it need o time, here d <dig> is the number of children in this family.
we need another o time to exchange the hcl-linkage information between the two parents and transfer that to its root r <dig> in the search tree t. so we need o time in total to process this nuclear family.
when we transfer the normalized hcl-linkage set  = {ψ <dig>  ψ <dig> ...ψk} to the upper nuclear families, we only need to remember that all ψi is coming from r <dig>  so for each ψi, it will only take o time to process rei, and o time to process lsi and phi.
the summation time is no more than o = o because lsi are disjoint subsets of { <dig> ,...,m}.
in other words, the hcl-linkages in one nuclear family won't increase the processing time of its adjacent families.
so the total running time to process all nuclear familes is no more than o = o, here x is the number of nuclear families in the whole pedigree.
we need another o time to complete step  <dig>  therefore, the time complexity of this algorithm is o.
for the computation, we need to maintain a data structure to store the hcl-linkage set Ψv for each node v; we can maintain the storage always below o for nuclear family fi.
so the space complexity of the algorithm is also o = o.
effectiveness of the haplotyping phase
excoffier used the em algorithm to estimate haplotype frequencies while ignoring the pedigree information.
here we adopt a two-stage method, which tries to reduce the number of possible haplotypes to be considered in the stage of estimation by utilizing the relatives' information to do haplotyping at first.
suppose we are estimating haplotype frequencies in trios and each haplotype consists of m biallelic snp loci.
for locus i, suppose that i happens to be one state with a probability of pi, and to be the other state with a probability of .
then locus i of the genotype is heterozygous with the probability of 2pi.
suppose the expected value of pi is p, then the genotype is expected to have 2p·m heterozygous loci.
as a consequence, a total number of 22p·m- <dig> possible haplotype pairs is expected to be considered if we use the em algorithm directly.
however, the probability that locus i in a trio is ambiguous is 2pi·2pi·2/ <dig> = 2pi <dig>  so the expected number of possible haplotype configurations for the trio is .
if p = 1/ <dig>  our method can handle λ = )/2) =  <dig> times longer genotypes than excoffier's methods.
moreover, in most cases, the more frequent allele at one locus appears with a probability of more than  <dig> , so our method usually can handle λ = 1/p >  <dig> times longer genotypes.
furthermore, if each locus of the haplotype is a micro-satellite locus, and it has l different alleles: a <dig>  a <dig> ...,al, each appears with the probability of p <dig>  p <dig> ...,pl.
then the expected number of possible haplotype pairs for a genotype is , the expected number of feasible haplotype configurations for a trio is , so our method usually can handle  times longer genotypes.
for example, when l =  <dig>  and p <dig> = p <dig> = ... = p <dig> = 1/ <dig>  λ =  <dig>  i.e.
our method can be applied to cases of much larger scale.
CONCLUSIONS
we present a two-stage method to do haplotyping and to estimate haplotype frequencies for pedigree genotype data in this paper.
given a set of pedigrees, it firstly determines all feasible haplotype configurations for each pedigree, then uses the em algorithm to estimate the haplotype frequencies based on the inferred haplotype configurations.
because a large number of illegal haplotypes have been eliminated from the possible haplotype list, our method is both more efficient and more accurate.
the experimental results show that, hanap runs much faster than em-decoder, and thus can be applied to much larger scale of instances.
moreover, the deviation of the estimate of hanap is smaller than that of em-decoder, which means it is more accurate.
our method suggests that pedigree information is of great importance in haplotype analysis.
it can be used to speedup estimation process, and to improve estimation accuracy as well.
the result also demonstrates that whole haplotype configuration space can be substitute by the space of zero-recombinant haplotype configurations in haplotype frequency estimation, especially when the considered haplotype block is relatively short.
authors' contributions
qz proposed the whole estimation framework and both the haplotyping and the estimation algorithms, and wrote the manuscript.
yz implemented the software and helped writing the manuscript.
gc and yx participated to the design of the study and wrote the manuscript.
all authors read and approved the final manuscript.
appendix
correctness of the hcl-linkage analysis haplotyping algorithm
first, we point out that every consistent haplotype configuration for pedigree p should be consistent with all hcl-linkages calculated by the unique partial solutions within trios, and our merge and transfer operations keep this feature during the whole process, i.e.
if ζ is a haplotype configuration for p, and ζ is consistent with all the hcl-linkages in the pedigree, it should also be consistent with those after the merge and transfer operations.
obviously, hcl-linkages are sufficient to generate a consistent haplotype configuration within a trio.
we prove that:
lemma
if it exists consistent haplotype configuration for a nuclear family , every imputing schema s of arbitrarily imputing the  alleles at one node can output one feasible solution ζ. contrarily, if one imputing schema ends with incompatibleness, there is no consistent haplotype configuration.
proof
firstly, hcl-linkages are necessary for constructing the consistent haplotype configurations, which means that if there is a feasible solution, it should correspond to one imputing schema.
secondly, we show that if one imputing schema outputs a feasible solution, all the schemas output feasible solutions.
in particular, for a trio , without loss of generality, we suppose that step  <dig> starts by imputing the "alleles" of node f. for a specified "locus" i, the two alleles of f, m and c <dig> are denoted as ,  and , and the partial haplotypes from locus  <dig> to locus  are denoted as ,  and .
suppose in schema s, allele a is imputed to ph <dig>  denoted as ph <dig> ← a, and ph <dig> ← b, ph <dig> ← c, ph <dig> ← d, ph <dig> ← e, ph <dig> ← f. if s outputs a consistent haplotype configuration for trio , we proof that s': ph <dig> ← a, ph <dig> ← b, ph <dig> ← c, ph <dig> ← d, ph <dig> ← e, ph <dig> ← f outputs another consistent haplotype configuration.
the loci from  <dig> to  can be viewed as a compound locus i. let's refer to table  <dig>  because we can impute a or b to ph <dig>  either or both of "locus" i and i should be ambiguous.
else, they will be linked to a bigger compound "locus" in step  <dig> or  <dig> by hcl-linkages.
whatever a or b will be linked with ph <dig>  we can not impute that arbitrarily in step  <dig>  without loss of generality, we assume that locus i is ambiguous, which means that a ≠ b, and {a, b} = {c, d} = {e, f} .
we can prove that s' is also a consistent haplotype configuration by enumeration.
because nuclear family  is the intersection of trio , ,...,, the above prove shows that both both s: ph <dig> ← a, ph <dig> ← b, ph <dig> ← c, ph <dig> ← d and s': ph <dig> ← a, ph <dig> ← b, ph <dig> ← c, ph <dig> ← d will lead to a consistent haplotype configuration for the family.
we call s to s' a walk step by switching ph <dig> ← a to ph <dig> ← b. obviously, for any two imputing schemata s <dig> and s <dig>  we can transfer s <dig> to s <dig> by consecutive walk steps.
so s1and s <dig> will lead to a consistent haplotype configuration or neither can.
this lemma indicates that our algorithm works in a nuclear family.
we now can prove the correctness of our hcl-linkage analysis haplotyping algorithm by induction, i.e.
if there is at least one feasible solution for a general pedigree, hcl-linkages are sufficient to generate all solutions.
suppose that the root r has multiple child mating nodes: o <dig> ...,or, each represents a nuclear family; and the algorithm works in all sub-trees, i.e.
all of the feasible solutions for those sub-trees can be directly deduced from the hcl-linkages collected from the sub-trees and stored at their roots.
from the former lemma, we know that if incompatibleness of type ii occurs, there is no feasible solution.
we assume that there is no incompatibleness of type ii and there are always feasible solutions for all sub-trees.
suppose that haplotype configuration ζ is consistent with all the hcl-linkages at root r .
then ζ should be consistent haplotype configuration when restricted to any nuclear family of o <dig> ...,or, and it should also be consistent with the hcl-linkages at the root of lower sub-trees of o <dig> ...,or.
by induction, ζ should be a feasible solution when restricted to any of these sub-trees.
so ζ is a consistent haplotype configuration of the whole pedigree p.

 the modelling of human genetic variation is critical to the understanding of the genetic basis for complex diseases. single nucleotide polymorphisms are the most frequent form of variation. the human genome project and other large-scale efforts have identified millions of snp markers. although each marker can be analyzed independently, it is more informative to analyze them in groups. therefore, it is useful to analyze haplotypes, which are sequences of linked markers on a single chromosome. in diploid organisms, such as human beings, chromosomes come in pairs, and experiments often yield genotype information, which blend haplotype information for chromosome pairs. there is growing evidence that, in order to better characterize the role of a candidate gene, full haplotype information should be exploited instead of using only genotype information. unfortunately, it is both time-consuming and expensive to derive haplotype information experimentally. this explains the increasing interest in inferring haplotype information, or haplotyping, computationally. in fact, the potential use of haplotypes has led to the initiation of the hapmap project which is to investigate haplotype patterns in the human genome in different populations. haplotype inference and frequency estimation are essential components of this endeavour. genotype data can be with or without any pedigree information, the first category is called population genotype data while the second one is pedigree genotype data. a large number of algorithms have been designed to estimate haplotype frequencies based on population data. among them, em algorithms are most popular due to their interpretability and stability. for any given pedigree genotype data, we can certainly discard the pedigree information and simply take the genotype sequences as the input of em estimation algorithms for population data. however, it is well accepted that information obtained by analyzing pedigree genotype data is more reliable: the constraint provided by other members in a pedigree would force one genotype to settle on a unique haplotype pair as being most probable. here we propose a two-stage method to estimate haplotype frequencies in pedigrees. the first stage is the haplotyping stage, which finds out all feasible haplotype configurations for each pedigree. in the second estimation stage, we use em algorithm to estimate haplotype frequencies in pedigrees based on the haplotype configurations inferred in the former stage. in general, haplotyping pedigrees need consider the entire solution space of all possible consistent haplotype configurations. however, the genomic dna can be partitioned into long blocks such that recombinations within each block are rare or even nonexistent. thus it is believed that haplotype configurations with fewer recombinations should be preferred in haplotype inference. when the region of interest is so small that the expected number of recombinations in the pedigree data is very close to zero, the solution space of all consistent haplotype configurations can be replaced by that of zero recombination to estimate haplotype frequencies. it is because the contribution of the solutions of recombinations to the overall likelihood becomes so small compared to those of zero recombination while they bring considerable complexity to the computation. thus, we are interested in finding the consistent haplotype configurations of zero recombination. wijsman proposed a 20-rule algorithm, and o'connell described a genotype-elimination algorithm, both of which can be used to find out zero-recombinant haplotype configurations for pedigrees. recently, li and jiang showed that it could be solved in polynomial time. here we propose an algorithm to find out zero-recombinant haplotype configurations in linear time using a technique called hcl-linkage analysis. in the second stage, we use the em algorithm to estimate haplotype frequencies based on haplotype configurations obtained from the haplotyping stage. we employ the hardy-weinberg equilibrium to obtain the probabilities of founder genotypes and use a genetic model to deduce the transmitted probabilities of non-founders. while the likelihood of each configuration is computed by multiplying the probabilities of each genotype, the frequency of each haplotype that appears in the configuration is calculated by a gene-counting method. we implement all the algorithms in a c software package named hanap and test its effectiveness and efficiency both on simulated and real data sets. the experimental results show that, our method runs much faster than the direct frequency estimation software that discards the pedigree information. moreover, because our method utilizes such information, the estimation is more reliable. methods haplotyping stage: haplotyping algorithm based on hcl-linkage analysis excoffier's em algorithm was widely applied in haplotype analysis. unfortunately, it should calculate the frequencies of all possible haplotype pairs consistent to each given genotype, which is unbearable in storage when the haplotype length grows to more than. o'connell showed that genetic information from relatives could be used to resolve one genotype's ambiguity, and thus reduce the number of haplotypes that should be considered. however, o'connell's method had an exponential time complexity. recently, li and jiang showed that, for any genotype in a given pedigree, its ambiguity could be solved in cubic time ), where n is the number of members in the pedigree and m is the number of loci in each genotype. here we present a so-called hcl-linkage analysis method to do haplotyping in linear time ). hcl-linkage definition trios are simple pedigrees that contain only a pair of parents and a child. a consistent zero-recombinant haplotype configuration for a general pedigree should also be a consistent zero-recombinant haplotype configuration when restricted to each trio in this pedigree. given trio t =, here f is the father, m is the mother and c is the child, suppose that locus i of f, m, and c have alleles {a, b}, {c, d} and {e, f} ). the genotype information of c can be homozygous or heterozygous. if it is homozygous, then it is clear that the paternal allele and the maternal allele are the same. the situation becomes complicated if it is a heterozygous site. table lists out all possible situations. we can see that given the locus genotype information for the three members, it may or may not be possible to determine the paternal allele and the maternal allele for the child. we call a locus ambiguous if its inheritance relationship cannot be resolved. in fact, for any trio, ignoring the ambiguous loci, the consistent haplotype configuration for the unambiguous loci is unique and specifies a linkage of alleles on some heterozygous loci for each node in the trio. we define such linkage as hcl-linkages. definition an hcl-linkage ψ is a quadruplet <v, re, ls, ph>defined on node v and specified by the unique consistent haplotype configuration within a trio that contains v. here v denotes the node to which the hcl-linkage belongs. ls = {a...,al} is the set of heterozygous loci where the haplotype configuration has been inferred. ph = {ph, ph'} = {, } records the two haplotypes imputed on these loci. re = denotes that ph is inherited from or will be passed on to the node in set r. an hcl-linkage describes the partial haplotype configuration of a node and the inheritance relationship between the parents and their children. under our definition, we can conclude that every haplotype configuration should be consistent with any hcl-linkage specified by each trio in the pedigree. merge and transfer operations over hcl-linkages in the case of multiple generations and multiple children, loci on one node may be linked by different hcl-linkages. hcl-linkages of the same node should be merged if they can. there are three cases when merging two hcl-linkages ψ = <v,, ls {ph ph1'}> and ψ = <v,, ls {ph ph2'}> on node v. case: ∩ ≠ Φ l.a) r ∩ r ≠ Φ or r1' ∩ r2' ≠ Φ, it means that both ph and ph are from the nodes in r and r said ph1' and ph2' are from the nodes in r1' and r2', so ph and ph should be on the same haplotype, and ph1' and ph2' on the other: i) ls ∩ ls = Φ, or ls ∩ ls ≠ Φ but ph equals ph when restricted to loci in ls ∩ ls it means that ψ and ψ are compatible. in this case, they should be merged to ψ = <v,, ls ∪ ls {ph ∪ ph ph1' ∪ ph2'}>, here ph ∪ ph denote a longer partial haplotype, which alleles equal to those of ph and ph when restricted to loci in ls and ls2; ii) ls ∩ ls ≠ Φ and ph doesn't equal ph when restricted to ls ∩ ls it means that ψ and ψ are incompatible, i.e. no haplotype configuration can satisfy the two hcl-linkages in the same time. b) r ∩ r2' ≠ Φ or r1' ∩ r ≠ Φ, it means that ph and ph2' should be on the same haplotype, and ph1' and ph on the other. similarly, ψ and ψ can be merged to ψ = <v,, ls ∪ ls {ph ∪ ph2', ph1' ∪ ph2}> when they are compatible. case: ∩ = Φ, but ls ∩ ls ≠ Φ, a) ph equals ph or ph equals ph2' when restricted to ls ∩ ls it means that ψ and ψ are compatible, in this case, they should be merged to ψ = <v,, ls ∪ ls {ph ∪ ph ph1' ∪ ph2'}> or ψ = <v,, ls ∪ ls {ph ∪ ph2', ph1' ∪ ph2}>. b) else, ph doesn't equal ph or ph2' when restricted to ls ∩ ls it means that ψ and ψ are incompatible. case: ∩ = Φ, and ls ∩ ls = Φ, in this case, ψ and ψ cannot be merged and both should be recorded in a hcl-linkage set Ψv for node v. with the merge operation, we can define the normalizing of a set of hcl-linkages Ψv: normalizing a set Ψv of hcl-linkages on node v means repeatedly applying the merge operation for pairs of hcl-linkages in Ψv until, ∀ψi, ψj ∈ Ψv, ∩ = Φ, and ls ∩ ls = Φ. Ψv is then said to be normalized. from now on, if there is no further notice, Ψv should be normalized after any changes. like genetic information, hcl-linkages will be passed on from generations to generations. without loss of generality, let us define the transfer of hcl-linkage information from child c to its parent f. the other case from f to c would be similar. let Ψc and Ψf represent the normalized hcl-linkage sets of c and f respectively, and let hs be the set of homozygous loci of f. the transfer of Ψc from c to f results in changes to Ψf, where each ψc = <c,, lsc, {phc, phc'}> ∈ Ψc is transferred independently. there are two cases to consider. case: if f ∈ rc, add ψf = <f,, lsc - hs, {phf, phf'}> to Ψf, here phf equals the resulting partial haplotypes of phc when restricted to loci in lsc - hs and phf' is the compensatory partial haplotypes of phf consistent to genotype gf. case: else, f ∉ rc ∪ rc': i) both phc and phc' are consistent with the partial genotype gf when restricted to loci in lsc, then add ψf = <f,, lsc - hs, {phf, phf'}> to Ψf, here phf and phf' equal the resulting partial haplotypes of phc and phc' when restricted to loci in lsc - hs; ii) phc' is not consistent with the partial genotype gf when restricted to loci in lsc, then add ψf = <f,, lsc - hs, {phf, phf'}> to Ψf, here phf equals the resulting partial haplotypes of phc when restricted to loci in lsc - hs and phf' is the compensatory partial haplotypes of phf consistent to genotype gf. note that at least one of phc and phc' should be consistent with the partial genotype gf. remember that Ψf should be normalized whenever adding a new hcl-linkage to it. in the case of transferring an hcl-linkage ψf from f to c, resulting in adding ψc = <c,, lsc, {phc, phc'}> to Ψc, note that we should add m into rc' whenever we have determined that f ∈ rc. our merge and transfer operations will not bring more or lose any hcl-linkage information for building consistent haplotype configurations. main hcl-linkages analysis haplotyping algorithm before the algorithm, we preprocess each trio in the pedigree. whenever a trio specifies an hcl-linkage for node v, it will be stored in the hcl-linkage set Ψv. the objective of the algorithm is to collect the complete hcl-linkage information for each node, which is accomplished by traversing the tree twice. firstly, we will convert the input pedigree into a rooted searching tree t. then we traverse t in post-order to transfer and merge the hcl-linkage information for each node from its relatives. we do this from the left lowest nuclear family fo. the hcl-linkages in nuclear family fo will be merged at both parents, and then be transferred to the root of the sub-tree. the same operations will be conducted in its parental nuclear family on hcl-linkages specified in this family as well as on those transferred from its child families. and at last, we collect all the hcl-linkages at the root r. in step we traverse t again in pre-order and transfer the linkage in another direction from r to its farmost descendants. after step the hcl-linkage set of each node preserves all hcl-linkages in the pedigree. in step we choose a node v arbitrarily. set Ψv contains several hcl-linkages ψ ψ...,ψl defined on disjoint locus set ls ls...lsl. when a set of loci are linked by one hcl-linkage, they can be viewed as a compound locus, and the two partial haplotypes can be viewed as two compound alleles. these "loci" will be treated equally as the other heterozygous loci and homozygous loci that are not involved in any hcl-linkage. we arbitrarily select one allele from the two at each locus to form a haplotype; the other alleles form another haplotype. it is called an imputing schema. whenever the haplotype configuration of one node is determined, it can be used to determine the configurations of its relatives, and those of the whole pedigree at last. during our algorithm, incompatibleness may occur when normalizing hcl-linkage set Ψv. then we declare that there is no solution and exit from the algorithm immediately. even in step incompatibleness may still occur when applying the haplotypes of the parents to resolve the genotype of the children in the case that an individual node has multiple children. figure shows an example. the key point is, if it exists a consistent haplotype configuration for a nuclear family, every arbitrary imputing schema s can output one feasible solution ζ. contrarily, if one imputing schema ends with incompatibleness, other schemata will fail too. we will prove this in the appendix. the time complexity and space complexity of our algorithm are both o where n is the number of the members in the pedigree and m is the length of the loci. frequency estimation stage suppose that we are given k pedigrees p = {p p...,pk}. each pi consists of ni nodes vi,j, in which the first ni' are founders. the genotype of node vi,j is gi,j. suppose that there are πi consistent solutions for pedigree pi and the s-th solution is: ss,i = <ss,i, ss,i,...,>, where ss,i,j = <αs,i,j, βs,i,j,2> is a haplotype pair of genotype gi,j. all haplotypes appear in these solutions form a list of haplotypes h = {h h...,hl} with frequencies Θ = {θ θ...,θl}, here θ + θ +... + θt = is what we want to estimate. the likelihood of haplotype frequencies given the observed pedigree data is, under the assumption of random mating, the paternal haplotype configuration and the maternal haplotype configuration are independent, and the child's haplotype configuration is transmitted from its parents. we have: here pr is the probability of haplotype configuration of the founder nodes, it can be computed using the hardy-weinberg equilibrium. pr is the gamete transmission probabilities of haplotype configuration ss,i,j with the parental haplotype configurations of and. it can be computed using a genetic model presented by elston and stewart. em algorithm estimates the haplotype frequencies Θ starting with the initial arbitrary values Θ = {θ θ...,θl}. these initial values are used as if they were the unknown true frequencies to estimate solution frequencies pr. these expected solution frequencies are used in turn to estimate haplotype frequencies at the next iteration Θ = {θi, θ...,θ}, and so on, until convergence is reached. suppose that in the r-th iteration, Θ = Θ and we want to estimate Θ. then we have: let δi,j,t be an indicator variable equalling the number of haplotype ht appear in solution ss,i. then the haplotype frequencies can be computed using a gene-counting method, there are several ways to initialize the haplotype frequencies Θ = {θ θ...,θl}. for instance, the initial haplotype frequencies can be chosen at random, or all haplotypes are equally frequent, i.e. Θt = 1/l. or that all initial haplotype frequencies are equal to the product of the corresponding single-locus allele frequencies. also, we can set all feasible solutions for each pedigree to be equally likely, i.e. pr) = 1/πi,. we can even initialize the haplotype frequencies by counting their occurrence in all the feasible solutions. since in practical applications the em algorithm could be trapped in some local maximum, we recommend to restart the algorithm several times with different initial haplotype frequencies and better with a randomized additive perturbation. the stopping criterion is defined as the absolute value of the difference of Θ between consecutive iterations being less than some small value ε >  simulated data set in order to generate a pedigree genotype data set for simulation experiments, we generate a population of haplotypes h* first, where each locus of each haplotype is set to some allele according to the probability distribution function p. in our simulation, we generated haplotypes of snp loci as well as haplotypes of micro-satellite loci. for a biallelic snp locus i, suppose that i happens to be one state with a probability of pi, and to be the other state with a probability of. for a micro-satellite loci, suppose it has w different alleles: a a...,aw, each appears with the probability of p p...,pw. each founder node in any tested pedigree is arbitrarily assigned a pair of haplotypes according to their frequencies θ*. the two haplotypes of a non-founder node are arbitrarily selected from those of its parents. at last, the pair of haplotypes of the same node is blended to form a genotype corresponding to that node. all experiments are conducted on a windows server with g hz cpu and mb ram. and for each parameter setting, copies are randomly generated and the performance is evaluated by computing the average numbers in these runs. running time of the haplotyping algorithm one of the main contributions of our paper is to do haplotyping in linear time, so we firstly examine the running time with respect to different number of nodes of each pedigree and different number of loci in each sequence. several different tree pedigree structures are used in the simulation, the first pedigree is figure in, which is a tree with nodes. the second one is figure in, which is a tree with nodes. the third one is a node pedigree from figure of. the results are given in figure it is obvious that our hcl-analysis haplotyping algorithm runs in linear time and thus could be applied to large-scale haplotype analysis. number of solutions we compare the numbers of haplotypes that should be considered in the estimation stage, with and without the haplotyping stage. in our experiment, we set p and p for snp loci, and set w = p and p for micro-satellite loci. we let |h*| = and θ1* =, θ2* = θ3* = θ4* =, θ5* = θ6* = θ7* = θ8* =, θ9* = θ10* =... = θ20* =. when only trio pedigrees are considered, the average numbers of haplotypes are recorded in table we can see from the table that the numbers of haplotypes that should be estimated have been greatly reduced after the haplotyping stage, which will immediately bring the improvement on the running time. we also consider a more complex pedigree that contains nodes. the average numbers of haplotypes are recorded in table we find that the number of haplotypes that should be estimated is even much smaller. we also notice that the number of haplotypes is growing with the length of haplotypes and the number of pedigrees. however, it grows very slowly. running time of hanap em-decoder is a popular software using the em algorithm to estimate the haplotype frequencies based on population data. as we have pointed out, it can be used to estimate haplotype frequencies in pedigrees, simply by discarding the pedigree information. here we also compare the running times of hanap and em-decoder. accuracy rate of hanap we define a parameter Δ to incarnate the deviation of the estimate haplotype frequencies from the underlying ones. because the simulation data are generated according to the Θ*, we recognize that as the underlying true frequencies. suppose the estimate haplotype set is he with frequencies Θe. compare he with h*. suppose the estimate frequencies of the haplotypes in h* are θ1e, θ2e,...,θ20e. we let, two real data sets we also test the efficiency and accuracy of hanap on two real data sets. the first real data set is from dbmhc|abdr, a set of trios. each genotype of these trios contains markers of the same position on chromosome of which are micro-satellite markers and others are snps. we run hanap to find the most frequent haplotypes. a list of haplotypes is found by hanap. their frequencies are shown in table it only takes hanap second to find these haplotypes while it is out of the capability of em-decoder. the second data set is from the ceph database, which contains families; each consists of only three generations, usually with four grandparents, two parents and a number of children. figure in shows a typical family with nodes. a great portion of the alleles in this data set have not been identified, and will be viewed as missing data. we carefully selected a data set of families on a block from chromosome with no recombination. both hanap and phase are applied to this data set. hanap inferred haplotypes with frequency larger than and phase inferred ones, among which are common. although we are not sure which output is closer to the real cases, the running time of hanap is extremely shorter than that of phase. discussion complexities of the hcl-linkage analysis haplotyping algorithm we show that the algorithm runs in o time and o space. the pre-process need calculate no more than 3n hcl-linkages in no more than n trios. each hcl-linkage can be computed in o time, so the pre-process can be done in o time. it takes step o time to construct the rooted tree. in step and step we have to traverse the whole tree, and visit each node for no more than constant times. when we process the hcl-linkages from the left lowest nuclear family, we should merge the d hcl-linkages at each parent node, it need o time, here d is the number of children in this family. we need another o time to exchange the hcl-linkage information between the two parents and transfer that to its root r in the search tree t. so we need o time in total to process this nuclear family. when we transfer the normalized hcl-linkage set = {ψ ψ...ψk} to the upper nuclear families, we only need to remember that all ψi is coming from r so for each ψi, it will only take o time to process rei, and o time to process lsi and phi. the summation time is no more than o = o because lsi are disjoint subsets of {,...,m}. in other words, the hcl-linkages in one nuclear family won't increase the processing time of its adjacent families. so the total running time to process all nuclear familes is no more than o = o, here x is the number of nuclear families in the whole pedigree. we need another o time to complete step therefore, the time complexity of this algorithm is o. for the computation, we need to maintain a data structure to store the hcl-linkage set Ψv for each node v; we can maintain the storage always below o for nuclear family fi. so the space complexity of the algorithm is also o = o. effectiveness of the haplotyping phase excoffier used the em algorithm to estimate haplotype frequencies while ignoring the pedigree information. here we adopt a two-stage method, which tries to reduce the number of possible haplotypes to be considered in the stage of estimation by utilizing the relatives' information to do haplotyping at first. suppose we are estimating haplotype frequencies in trios and each haplotype consists of m biallelic snp loci. for locus i, suppose that i happens to be one state with a probability of pi, and to be the other state with a probability of. then locus i of the genotype is heterozygous with the probability of 2pi. suppose the expected value of pi is p, then the genotype is expected to have 2p·m heterozygous loci. as a consequence, a total number of 22p·m- possible haplotype pairs is expected to be considered if we use the em algorithm directly. however, the probability that locus i in a trio is ambiguous is 2pi·2pi·2/ = 2pi so the expected number of possible haplotype configurations for the trio is. if p = 1/ our method can handle λ = )/2) = times longer genotypes than excoffier's methods. moreover, in most cases, the more frequent allele at one locus appears with a probability of more than, so our method usually can handle λ = 1/p > times longer genotypes. furthermore, if each locus of the haplotype is a micro-satellite locus, and it has l different alleles: a a...,al, each appears with the probability of p p...,pl. then the expected number of possible haplotype pairs for a genotype is, the expected number of feasible haplotype configurations for a trio is, so our method usually can handle times longer genotypes. for example, when l = and p = p =... = p = 1/ λ = i.e. our method can be applied to cases of much larger scale.  we present a two-stage method to do haplotyping and to estimate haplotype frequencies for pedigree genotype data in this paper. given a set of pedigrees, it firstly determines all feasible haplotype configurations for each pedigree, then uses the em algorithm to estimate the haplotype frequencies based on the inferred haplotype configurations. because a large number of illegal haplotypes have been eliminated from the possible haplotype list, our method is both more efficient and more accurate. the experimental results show that, hanap runs much faster than em-decoder, and thus can be applied to much larger scale of instances. moreover, the deviation of the estimate of hanap is smaller than that of em-decoder, which means it is more accurate. our method suggests that pedigree information is of great importance in haplotype analysis. it can be used to speedup estimation process, and to improve estimation accuracy as well. the result also demonstrates that whole haplotype configuration space can be substitute by the space of zero-recombinant haplotype configurations in haplotype frequency estimation, especially when the considered haplotype block is relatively short. authors' contributions qz proposed the whole estimation framework and both the haplotyping and the estimation algorithms, and wrote the manuscript. yz implemented the software and helped writing the manuscript. gc and yx participated to the design of the study and wrote the manuscript. all authors read and approved the final manuscript. appendix correctness of the hcl-linkage analysis haplotyping algorithm first, we point out that every consistent haplotype configuration for pedigree p should be consistent with all hcl-linkages calculated by the unique partial solutions within trios, and our merge and transfer operations keep this feature during the whole process, i.e. if ζ is a haplotype configuration for p, and ζ is consistent with all the hcl-linkages in the pedigree, it should also be consistent with those after the merge and transfer operations. obviously, hcl-linkages are sufficient to generate a consistent haplotype configuration within a trio. we prove that: lemma if it exists consistent haplotype configuration for a nuclear family, every imputing schema s of arbitrarily imputing the alleles at one node can output one feasible solution ζ. contrarily, if one imputing schema ends with incompatibleness, there is no consistent haplotype configuration. proof firstly, hcl-linkages are necessary for constructing the consistent haplotype configurations, which means that if there is a feasible solution, it should correspond to one imputing schema. secondly, we show that if one imputing schema outputs a feasible solution, all the schemas output feasible solutions. in particular, for a trio, without loss of generality, we suppose that step starts by imputing the "alleles" of node f. for a specified "locus" i, the two alleles of f, m and c are denoted as, and, and the partial haplotypes from locus to locus are denoted as, and. suppose in schema s, allele a is imputed to ph denoted as ph ← a, and ph ← b, ph ← c, ph ← d, ph ← e, ph ← f. if s outputs a consistent haplotype configuration for trio, we proof that s': ph ← a, ph ← b, ph ← c, ph ← d, ph ← e, ph ← f outputs another consistent haplotype configuration. the loci from to can be viewed as a compound locus i. let's refer to table because we can impute a or b to ph either or both of "locus" i and i should be ambiguous. else, they will be linked to a bigger compound "locus" in step or by hcl-linkages. whatever a or b will be linked with ph we can not impute that arbitrarily in step without loss of generality, we assume that locus i is ambiguous, which means that a ≠ b, and {a, b} = {c, d} = {e, f}. we can prove that s' is also a consistent haplotype configuration by enumeration. because nuclear family is the intersection of trio,,...,, the above prove shows that both both s: ph ← a, ph ← b, ph ← c, ph ← d and s': ph ← a, ph ← b, ph ← c, ph ← d will lead to a consistent haplotype configuration for the family. we call s to s' a walk step by switching ph ← a to ph ← b. obviously, for any two imputing schemata s and s we can transfer s to s by consecutive walk steps. so s1and s will lead to a consistent haplotype configuration or neither can. this lemma indicates that our algorithm works in a nuclear family. we now can prove the correctness of our hcl-linkage analysis haplotyping algorithm by induction, i.e. if there is at least one feasible solution for a general pedigree, hcl-linkages are sufficient to generate all solutions. suppose that the root r has multiple child mating nodes: o...,or, each represents a nuclear family; and the algorithm works in all sub-trees, i.e. all of the feasible solutions for those sub-trees can be directly deduced from the hcl-linkages collected from the sub-trees and stored at their roots. from the former lemma, we know that if incompatibleness of type ii occurs, there is no feasible solution. we assume that there is no incompatibleness of type ii and there are always feasible solutions for all sub-trees. suppose that haplotype configuration ζ is consistent with all the hcl-linkages at root r. then ζ should be consistent haplotype configuration when restricted to any nuclear family of o...,or, and it should also be consistent with the hcl-linkages at the root of lower sub-trees of o...,or. by induction, ζ should be a feasible solution when restricted to any of these sub-trees. so ζ is a consistent haplotype configuration of the whole pedigree p. 
the potential use of haplotypes has led to the initiation of the hapmap project which is to investigate haplotype patterns in the human genome in different populations. the result also demonstrates that the whole haplotype configuration space can be substituted by the space of zero-recombinant haplotype configurations in haplotype frequency estimation, especially when the considered haplotype block is relatively short. in the haplotyping stage, we propose a linear time algorithm to determine all zero-recombinant haplotype configurations for each pedigree. in the estimation stage, we use the expectation-maximization algorithm to estimate haplotype frequencies based on these haplotype configurations. we present a two-stage method to estimate haplotype frequencies in pedigrees, which includes haplotyping stage and estimation stage. our method suggests that pedigree information is of great importance in haplotype analysis. haplotype inference and frequency estimation are essential components of this endeavour. the experiments demonstrate that our method runs much faster and gives more credible estimates than other popular haplotype analysis software that discards the pedigree information. it can be used to speedup estimation process, and to improve estimation accuracy as well. haplotype analysis has gained increasing attention in the context of association studies of disease genes and drug responsivities over the last years.
 haplotype analysis has gained increasing attention in the context of association studies of disease genes and drug responsivities over the last years. the potential use of haplotypes has led to the initiation of the hapmap project which is to investigate haplotype patterns in the human genome in different populations. haplotype inference and frequency estimation are essential components of this endeavour.  we present a two-stage method to estimate haplotype frequencies in pedigrees, which includes haplotyping stage and estimation stage. in the haplotyping stage, we propose a linear time algorithm to determine all zero-recombinant haplotype configurations for each pedigree. in the estimation stage, we use the expectation-maximization algorithm to estimate haplotype frequencies based on these haplotype configurations. the experiments demonstrate that our method runs much faster and gives more credible estimates than other popular haplotype analysis software that discards the pedigree information.  our method suggests that pedigree information is of great importance in haplotype analysis. it can be used to speedup estimation process, and to improve estimation accuracy as well. the result also demonstrates that the whole haplotype configuration space can be substituted by the space of zero-recombinant haplotype configurations in haplotype frequency estimation, especially when the considered haplotype block is relatively short. june 20– symposium of computations in bioinformatics and bioscience in conjunction with the international multi-symposiums on computer and computational sciences hangzhou, china 