Excap: maximization of haplotypic diversity of linked markers.
Genetic markers, defined as variable regions of DNA, can be utilized for distinguishing individuals or populations. As long as markers are independent, it is easy to combine the information they provide. For nonrecombinant sequences like mtDNA, choosing the right set of markers for forensic applicat...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2013-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC3820696?pdf=render |
| _version_ | 1819056440270127104 |
|---|---|
| author | André Kahles Fahad Sarqume Peter Savolainen Lars Arvestad |
| author_facet | André Kahles Fahad Sarqume Peter Savolainen Lars Arvestad |
| author_sort | André Kahles |
| collection | DOAJ |
| description | Genetic markers, defined as variable regions of DNA, can be utilized for distinguishing individuals or populations. As long as markers are independent, it is easy to combine the information they provide. For nonrecombinant sequences like mtDNA, choosing the right set of markers for forensic applications can be difficult and requires careful consideration. In particular, one wants to maximize the utility of the markers. Until now, this has mainly been done by hand. We propose an algorithm that finds the most informative subset of a set of markers. The algorithm uses a depth first search combined with a branch-and-bound approach. Since the worst case complexity is exponential, we also propose some data-reduction techniques and a heuristic. We implemented the algorithm and applied it to two forensic caseworks using mitochondrial DNA, which resulted in marker sets with significantly improved haplotypic diversity compared to previous suggestions. Additionally, we evaluated the quality of the estimation with an artificial dataset of mtDNA. The heuristic is shown to provide extensive speedup at little cost in accuracy. |
| first_indexed | 2024-12-21T13:23:27Z |
| format | Article |
| id | doaj.art-42df63ee49d24ddca4cade1d4791ade0 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-21T13:23:27Z |
| publishDate | 2013-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-42df63ee49d24ddca4cade1d4791ade02022-12-21T19:02:32ZengPublic Library of Science (PLoS)PLoS ONE1932-62032013-01-01811e7901210.1371/journal.pone.0079012Excap: maximization of haplotypic diversity of linked markers.André KahlesFahad SarqumePeter SavolainenLars ArvestadGenetic markers, defined as variable regions of DNA, can be utilized for distinguishing individuals or populations. As long as markers are independent, it is easy to combine the information they provide. For nonrecombinant sequences like mtDNA, choosing the right set of markers for forensic applications can be difficult and requires careful consideration. In particular, one wants to maximize the utility of the markers. Until now, this has mainly been done by hand. We propose an algorithm that finds the most informative subset of a set of markers. The algorithm uses a depth first search combined with a branch-and-bound approach. Since the worst case complexity is exponential, we also propose some data-reduction techniques and a heuristic. We implemented the algorithm and applied it to two forensic caseworks using mitochondrial DNA, which resulted in marker sets with significantly improved haplotypic diversity compared to previous suggestions. Additionally, we evaluated the quality of the estimation with an artificial dataset of mtDNA. The heuristic is shown to provide extensive speedup at little cost in accuracy.http://europepmc.org/articles/PMC3820696?pdf=render |
| spellingShingle | André Kahles Fahad Sarqume Peter Savolainen Lars Arvestad Excap: maximization of haplotypic diversity of linked markers. PLoS ONE |
| title | Excap: maximization of haplotypic diversity of linked markers. |
| title_full | Excap: maximization of haplotypic diversity of linked markers. |
| title_fullStr | Excap: maximization of haplotypic diversity of linked markers. |
| title_full_unstemmed | Excap: maximization of haplotypic diversity of linked markers. |
| title_short | Excap: maximization of haplotypic diversity of linked markers. |
| title_sort | excap maximization of haplotypic diversity of linked markers |
| url | http://europepmc.org/articles/PMC3820696?pdf=render |
| work_keys_str_mv | AT andrekahles excapmaximizationofhaplotypicdiversityoflinkedmarkers AT fahadsarqume excapmaximizationofhaplotypicdiversityoflinkedmarkers AT petersavolainen excapmaximizationofhaplotypicdiversityoflinkedmarkers AT larsarvestad excapmaximizationofhaplotypicdiversityoflinkedmarkers |