Calculating Inbreeding on a 10 Generation Pedigree

[Triple_Deuce]

I am in the process of trying to create a pedigree website (php/mysql)...

I want to be able to calculate a dog's inbreeding coefficient on 10 generations.

 

I am so not sure where to even begin.

 

I have a database table:

dogs:

Fields:          id          name           sireid             damid

         

equation:

F_X  =  å [ (½) ⁿ₁⁺ⁿ₂⁺¹ (1 + F_A)] 

 

http://www.highflyer.supanet.com/coefficient.htm

 

 

 

Can someone give me a starting point?

Do I need to learn bianary trees? could I do this with an array?

 

Thanks

Edited November 20, 2014 by Triple_Deuce

[NotionCommotion]

Do I need to learn bianary trees? could I do this with an array?

 

Don't think you need binary trees, just simple math.  What are you summing over?  Probably could just do in in SQL, however, I suppose if you want, you could iterate over an array.

[Barand]

A couple of years back I was working on dog pedigree charts so still had some test data. The chart of the data is attached and, as you can see, there are common ancestors.

 

To find them you need to use a recursive function so I would load your data into an array and use that for the recursive search rather bombard your server with dozens of queries.

 

This code will give the common ancestors and the generational distance on the sire and dam sides. You would then need to calc the IC value for each of these ancestors.

$db = new mysqli(HOST,USERNAME,PASSWORD,DATABASE);

$sql = "SELECT id, dogname, sire, dam
        FROM dogtable";


$dogs = $sires = $dams = array();
$res = $db->query($sql);
while (list($id, $nm, $s, $d) = $res->fetch_row()) {
    $dogs[$id] = [$s,$d,$nm];
}

function getAncestors($id, $key, &$dogs, &$ancests, $dist)
{
    if ($id==0) return;
    $ancests[$id] = $dist;
    if (isset($dogs[$id]) ) {
        
        getAncestors($dogs[$id][$key], 0, $dogs, $ancests, $dist+1);
        getAncestors($dogs[$id][$key], 1, $dogs, $ancests, $dist+1);
    }
}

$dogid = 1;

getAncestors($dogs[$dogid][0], 0, $dogs, $sires, 0);
getAncestors($dogs[$dogid][1], 1, $dogs, $dams, 0);

ksort($sires); ksort($dams);

$common = array_intersect_key($sires,$dams);

echo "<pre>";
echo "|  ID |      NAME          | SIRE | DAM  |\n";
echo "|     |                    | DIST | DIST |\n";
echo "|-----|--------------------|------|------|\n";

foreach ($common as $id => $dist) {
    printf("|%4d | %-18s | %4d | %4d |\n", 
            $id,
            $dogs[$id][2],
            $sires[$id],
            $dams[$id]);
}

Outputs

|  ID |      NAME          | SIRE | DAM  |
|     |                    | DIST | DIST |
|-----|--------------------|------|------|
|   8 | dog I              |    2 |    1 |
|  16 | dog Q              |    3 |    2 |
|  17 | dog R              |    3 |    2 |

[Barand]

PS - apologies for the bisexual dog in the data, but you get the idea

[Barand]

Corrected version

$db = new mysqli(HOST,USERNAME,PASSWORD,DATABASE);

$sql = "SELECT id, dogname, sire, dam
        FROM dogtable";


$dogs = $sires = $dams = array();
$res = $db->query($sql);
while (list($id, $nm, $s, $d) = $res->fetch_row()) {
    $dogs[$id] = [$s,$d,$nm];
}

function getAncestors($id, &$dogs, &$ancests, $dist)
{
    if ($id==0) return;
    $ancests[$id] = $dist;
    if (isset($dogs[$id]) ) {
        
        getAncestors($dogs[$id][0], $dogs, $ancests, $dist+1);
        getAncestors($dogs[$id][1], $dogs, $ancests, $dist+1);
    }
}

$dogid = 1;

getAncestors($dogs[$dogid][0], $dogs, $sires, 1);
getAncestors($dogs[$dogid][1], $dogs, $dams, 1);

ksort($sires); ksort($dams);

$common = array_intersect_key($sires,$dams);

echo "<pre>";
echo "|  ID |      NAME          | SIRE | DAM  |\n";
echo "|     |                    | DIST | DIST |\n";
echo "|-----|--------------------|------|------|\n";

foreach ($common as $id => $dist) {
    printf("|%4d | %-18s | %4d | %4d |\n", 
            $id,
            $dogs[$id][2],
            $sires[$id],
            $dams[$id]);
}

|  ID |      NAME          | SIRE | DAM  |
|     |                    | DIST | DIST |
|-----|--------------------|------|------|
|   8 | dog I              |    3 |    2 |
|  16 | dog Q              |    4 |    3 |
|  17 | dog R              |    4 |    3 |

Edited November 21, 2014 by Barand

[simon831]

Did you ever get anywhere with calculating the coefficient of inbreeding?

 

I am also looking for some code or sql to help with it.

[Triple_Deuce]

@Barand

I apologize, I had not seen replies to this topic and just happened to stumble across it again on a google search.

 

I've tried your code and I'm not receiving results, my thought as to why is because 

$common = array_intersect_key($sires,$dams);

$sires[] & $dams[] will not intersect since they aren't of the same gender.

[Triple_Deuce]

I couldnt find out to edit my post above...

 

Correction... it works on your data but not my data.

[Barand]

Can you post/attach a dump of your data?

[Barand]

try this version

$db = new mysqli(HOST,USERNAME,PASSWORD,DATABASE);

$sql = "SELECT id, dogname, sire, dam
        FROM dogtable";


$dogs = $sires = $dams = array();
$res = $db->query($sql);
while (list($id, $nm, $s, $d) = $res->fetch_row()) {
    $dogs[$id] = [$s,$d,$nm];
}

function getAncestors($id, &$dogs, &$ancests, $dist)
{
    if ($id==0) return;
    $ancests[$id] = $dist;
    if (isset($dogs[$id]) ) {
        
        getAncestors($dogs[$id][0], $dogs, $ancests, $dist+1);
        getAncestors($dogs[$id][1], $dogs, $ancests, $dist+1);

    }
}

$dogid = 1;
$sires = $dams = [];

getAncestors($dogs[$dogid][0], $dogs, $sires, 1);
getAncestors($dogs[$dogid][1], $dogs, $dams, 1);

ksort($sires); ksort($dams);

#echo '<pre>',print_r($dogs, true),'</pre>';
echo '<pre>sires ',print_r($sires, true),'</pre>';
echo '<pre>dams ',print_r($dams, true),'</pre>';

$common = array_intersect_key($sires,$dams);
#$common = array_merge($sires,$dams);

echo "<pre>";
echo "|  ID |      NAME          | SIRE | DAM  |\n";
echo "|     |                    | DIST | DIST |\n";
echo "|-----|--------------------|------|------|\n";

foreach ($common as $id => $dist) {
    printf("|%4d | %-18s | %4d | %4d |\n", 
            $id,
            $dogs[$id][2],
            $sires[$id],
            $dams[$id]);
}

Edited December 8, 2015 by Barand

[Triple_Deuce]

I really appreciate the help.

I got it to work... 

 

now I have the following:

http://play.ratsofnimh.com/pedigree/inbreeding2.php

 

I'm trying to figure out how to take the given data and plug it into the equation... Sire Dist and Dam Dist would be plugged into N1 and N2... I guess i need to figure out where to put the equation because Fa will be the already calculated inbreeding COI

Edited December 8, 2015 by Triple_Deuce

[Barand]

Add another element to the $dogs array to store the COI (Fa) for that dog. It will require a recursive function along these lines

function COI(ancester_id) {
    if (COI is in the table already) {
        return COI from the table
    }
    else {
        calculate COI of ancester            // will require calls to COI(ancester)  the recursive bit
        store in table
        return calculated value;
    }
}

[Triple_Deuce]

Looks like I got this working... my only issue seems to be if a certain dog is behind the sire or dam multiple times... which i think stems from the array_intersect_key()....  I'd like to list every apparence of a dog, even if shown multple times and calculate that appear in the table to use that data in the calculate... does that make sense?

 

http://play.ratsofnimh.com/pedigree/inbreeding2.php

 

Putting in ID 34 returns the proper ICO: 0.0625 (6.25 %)

Putting in ID 9 returns the wrong ICO of 0.25 (25 %) because it's only counting dog ID 17 twice, instead of the 3 times it shows.  The ICO should be 0.375 (37.5%)... any suggestions?

Thanks

[Barand]

The problem is the function was only storing one occurrence per ancestor. Try this
 

$db = new mysqli(HOST,USERNAME,PASSWORD,DATABASE);

function getAncestors($id, &$dogs, &$ancests, $dist)
{
    if ($id==0) return;
    $ancests[$id][] = $dist;        // <-- changed to store more than 1 distance
    if (isset($dogs[$id]) ) {
        
        getAncestors($dogs[$id][0], $dogs, $ancests, $dist+1);
        getAncestors($dogs[$id][1], $dogs, $ancests, $dist+1);
    }
}

$sql = "SELECT id, dogname, sire, dam
        FROM dogtable";

$dogs = $sires = $dams = array();
$res = $db->query($sql);
while (list($id, $nm, $s, $d) = $res->fetch_row()) {
    $dogs[$id] = [$s,$d,$nm];
}

$dogid = 1;

getAncestors($dogs[$dogid][0], $dogs, $sires, 1);
getAncestors($dogs[$dogid][1], $dogs, $dams, 1);

ksort($sires); ksort($dams);

echo '<pre>sires ',print_r($sires, true),'</pre>';
echo '<pre>dams ',print_r($dams, true),'</pre>';

$common = array_intersect_key($sires,$dams);

echo "<pre>";
echo "|  ID |      NAME          | SIRE | DAM  |\n";
echo "|     |                    | DIST | DIST |\n";
echo "|-----|--------------------|------|------|\n";

foreach ($common as $id => $dist) {
    printf("|%4d | %-18s |%6s|%6s|\n", 
            $id,
            $dogs[$id][2],
            join(',', $sires[$id]),       //   changed to show the
            join(',', $dams[$id]) );      //   multiple distances
}

Now gives results like

|  ID |      NAME          | SIRE | DAM  |
|     |                    | DIST | DIST |
|-----|--------------------|------|------|
|   8 | dog I              |     3|     2|
|  10 | dog K              |   4,3|     3|
|  16 | dog Q              |     4|     3|
|  17 | dog R              |     4|     3|
|  20 | dog U              |   5,4|     4|
|  21 | dog V              |   5,4|     4|

Edited December 9, 2015 by Barand
added results example

[Barand]

Does this version give the results you expect?

<?php
$db = new mysqli(HOST,USERNAME,PASSWORD,DATABASE);

function getAncestors($id, &$dogs, &$ancests, $dist)
{
    if ($id==0) return;
    $ancests[$id][] = $dist;
    if (isset($dogs[$id]) ) {
        
        getAncestors($dogs[$id][0], $dogs, $ancests, $dist+1);
        getAncestors($dogs[$id][1], $dogs, $ancests, $dist+1);
    }
}

function COI($id, &$dogs)
{
    if ($id==0) return 0;
    $sires = $dams = [];
    getAncestors($dogs[$id][0], $dogs, $sires, 1);
    getAncestors($dogs[$id][1], $dogs, $dams, 1);
    $result=0;
    foreach ($sires as $did=>$dists) {
        if (isset($dams[$did])) {
            if (!is_null($dogs[$did][3])) {
                return $dogs[$did][3];
            }
            else {
                $sumd = array_sum($dists) + array_sum($dams[$did]);
                $result += pow(0.5, 1+$sumd) * (1 + COI($did, $dogs));
                $dogs[$did][3] = $result;
            }
        }
    }
    return $result;
}

$sql = "SELECT id, dogname, sire, dam
        FROM dogtable";

$dogs = array();
$res = $db->query($sql);
while (list($id, $nm, $s, $d) = $res->fetch_row()) {
    $dogs[$id] = [$s,$d,$nm,null];
}

$dogid = 9;

printf("Dog %d COI : %0.3f", $dogid, COI($dogid, $dogs));
?>

[Triple_Deuce]

Thank you for helping...

The above code does not give correct output.

 

I've got it working on some scenarios while not working on others.

My monkey wrench is basically with multiple positions.

 

http://play.ratsofnimh.com/pedigree/inbreeding2.php     inputting ID: 9

ICO = .375 ; this is correct

 

Then, branching a little further to input id: 4            /Id 4's dam is ID 9/

it totals .1875 ; this is wrong, it should be .15625

 

So if you look at id4  and it's relative 17, 17's data looks like this:

| ID | NAME               | SIRE | DAM  |
|    |                    | DIST | DIST |
|----|--------------------|------|------|
| 17 | Dog R              | 2    | 3,2,1|

I think it would fix the problem if I could get the respective numbers to line up and everyone else is paired with 0.

something like:

| ID | NAME               | SIRE | DAM  |
|    |                    | DIST | DIST |
|----|--------------------|------|------|
| 17 | Dog R              | 2    |     1|
| 17 | Dog R              | 0    |     2|
| 17 | Dog R              | 0    |     3|

I dont know if that makes any sense or not and I dont know if that would actually solve my problem.  I just know that probably not every number should be added to one another.

 

I'm positive it stems from my foreach statement since I have it nested, because numbers are being added together that shouldnt be but unsure of how to match the other numbers with 0 if needed.  I'm not sure what another option would be, just know it needs to be unnested. 

[Barand]

Can you post/attach a dump of your data?

[Triple_Deuce]

Dog Id	Dog Name	    Dog Sire	Dog Dam
1	Nimh's Delorean	    2	        3
2	Dog B	            4	        9
3	Dog C	            7	        8
4	Dog E	            7	        9
5	Dog F	            10	        11
7	Dog H	            14	        15
8	Dog I	            16	        17
9	Dog J	            16	        17
10	Dog K	            18	        19
11	Dog L	            20	        21
14	Dog O	            20	        17
15	Dog P	            0	        0
16	Dog Q	            14	        17
17	Dog R	            0	        0
18	Dog S	            0	        0
19	Dog T	            0	        0
20	Dog U	            0	        0
21	Dog V	            0	        0
22	Dog W	            0	        0
23	Dog X	            0	        0
24	Cedric	            25	        26
25	Phantom		    27	        0
26	Walton Mare         27	        0
27	Walton		    0	        0
28	A		    0	        0
29	B	            0	        0
30	C	            29	        28
31	D	            29	        28
32	E	            0	        30
33	F	            0	        31
34	I	            33	        32
35	J	            0	        0
36	K	            0	        0
37	L	            0	        0
38	M	            0	        0
39	N	            0	        0
40	Dog1	            0	        0
41	Dog2	            0	        0
42	Dog3	            40	        41
43	Dog4	            42	        41

hope this is what you were looking for. 0 means no ancestor registered, so isnt counted.

[Barand]

For dog 4, you had this for common ancestor 17
 

                             sire    dam
|  17 | Dog R              |     2| 3,2,1|

so you processed it as

               0.015625    |   2  |   3  |
               0.03125     |   2  |   2  |
               0.0625      |   2  |   1  |

Shouldn't it have been

               0.015625    |   2  |   3  |
               0.125       |   0  |   2  |
               0.25        |   0  |   1  |

[Barand]

So, which is correct for Dog #4?

METHOD 1
|    14 |   0.0625 |   1 |   2 |
|    20 |   0.0156 |   2 |   3 |
|    17 |   0.0156 |   2 |   3 |
|    17 |   0.0312 |   2 |   2 |
|    17 |   0.0625 |   2 |   1 |
Dog 4 COI : 0.1875

METHOD 2
|    14 |   0.0625 |   1 |   2 |
|    20 |   0.0156 |   2 |   3 |
|    17 |   0.0156 |   2 |   3 |
|    17 |   0.1250 |   0 |   2 |
|    17 |   0.2500 |   0 |   1 |
Dog 4 COI : 0.4688

[Triple_Deuce]

I'd of thought the 2nd method would have been correct but according to the site I'm using to check myself (http://www.czerwonytrop.com/inb/) neither are right.

I'm going to have to go back through the equation and work by hand and see where I'm screwing up.

 

i'll come back once I've ironed out my error in the equation. 

[Barand]

Looks like that site used

REF SITE
METHOD 3
|    14 |   0.0625 |   1 |   2 |
|    17 |   0.0312 |   2 |   2 |
|    17 |   0.0625 |   2 |   1 |
Dog 4 COI : 0.1562

Dog #20 ignored, and only two of the three occurrences of #17 were used.

 

So why?

Edited December 11, 2015 by Barand

[Triple_Deuce]

 

From my reading I'm beginning to wonder if that site is wrong.

Based on the sites I've read and calculated by hand I keep getting different than that site...  I get the .1875 so maybe that is more accurate than the site I was checking myself against?  

Especially since it wasnt counting certain instances? How did you find that Dog 20 was being ignored on that site and only 2 of the 3 instances of 17 were being used?

 

http://www.fao.org/docrep/006/x3840e/X3840E03.htm

 

 

F_X = ∑[(0.5)^N(1 + F_A)]

where:
F_X = the inbreeding of an individual;
∑ = the symbol for “sum of ” or “add”;
N = the number of individuals in a path that is determined by tracing a path from one parent back to the common ancestor and forward from the common ancestor to the other parent; if more than one common ancestor exists, the term (0.5)^N is repeated for each common ancestor; if more than one path exists between the individual and a common ancestor, the term (0.5)^N is repeated for each unique path;
F_A = the inbreeding of the common ancestor.

If the inbreeding value of the common ancestor is zero or unknown, in which case you must assume that it is zero, the formula is simplified to:

F_X = ∑(0.5)^N

 

Which I've been calculating F_A as 0 since we don't know for sure.

 

 

Thank you for your continued help.

Edited December 11, 2015 by Triple_Deuce

[Barand]

 

How did you find that Dog 20 was being ignored on that site and only 2 of the 3 instances of 17 were being used?

I used your site page to generate the pedigree for Dog#4 then entered that in their calculator chart. There was no dog #20 in their results (only 14 and 17) and then I looked at what results would give their value for #17.

[Triple_Deuce]

OK, after some digging, I think I've decided the green site isnt accurate...

 

I found this site http://www.fao.org/docrep/006/x3840e/X3840E03.htm (at the bottom)

"Pedigree illustrating the fact that the mating of two inbred, but unrelated, fish will produce offspring with no inbreeding: F_J = 25% and F_U = 37.5%, but because they are not related, F_Z= 0%."

 

Based on given info I get .5 (50%) as inbreeding on F_U (ID#: 59) instead of .375 (37.5%).... but my stuff is calculating F_J (ID#: 52) @ .25 (25%) & F_Z  (ID#: 60) @ 0 correctly.

 

If my program leaves out either O (#53) or P (#54) from the equation it calculates correctly at .375 (37.5%) for F_U but I'd of thought that both the great grandparents should have been counted... 

| ID | NAME | SIRE | DAM |
| | | DIST | DIST |
|-----|--------------------|------|------|
| 53 |  O                  |   2,2|   2,2|
0.03125
0.03125
0.03125
0.03125

|  54 | P                  |   2,2|   2,2|
0.03125
0.03125
0.03125
0.03125

|  55 | Q                  |     1|     1|
0.125

|  56 | R                  |     1|     1|
0.125

I'm going to try and get some better help to understand the equation because I'm missing something or misunderstanding something in the equation.