Globally optimal classification and pairing of human chromosomes

We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in...

Full description

Saved in:
Bibliographic Details
Main Authors: Xiaolin Wu, Biyani, P., Dumitrescu, S., Qiang Wu
Format: Conference Proceeding
Language:English
Subjects:
Biological cells
Cells (biology)
Classification algorithms
Genetics
Heuristic algorithms
Humans
Neural networks
Polynomials
Robustness
Transportation
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 2792
container_issue
container_start_page 2789
container_title
container_volume 1
creator Xiaolin Wu
Biyani, P.
Dumitrescu, S.
Qiang Wu
description We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in polynomial time. In addition, we propose a technique of homologue pairing via maximum-weight graph matching. It obtains the globally optimal solution by forming all homologue pairs simultaneously under a maximum likelihood criterion, rather than finding one pair at a time as in existing heuristic algorithms. After the optimal homologue pairing, chromosome classification can also be done by maximum-weight graph matching. This new graph theoretical approach to chromosome pairing and classification is more robust than the transportation algorithm, because many attributes of a chromosome have less variations within a cell than between different cells.
doi_str_mv 10.1109/IEMBS.2004.1403797
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_1403797</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1403797</ieee_id><sourcerecordid>1403797</sourcerecordid><originalsourceid>FETCH-ieee_primary_14037973</originalsourceid><addsrcrecordid>eNp9jrsKwjAYhQMieOsL6JIXsP4xhTabKPUydNK9_NbURnIpSR369nbo7FkOHwc-DiFrBjFjIHa3vDje4z1AErMEeCrSCVlAmgHPEi74jEQhfGAIFwNnc3K4aPdErXvq2k4Z1LTSGIKqVYWdcpaifdEWlVf2TV1Nm69BS6vGO-OCMzKsyLRGHWQ09pJszvnjdN0qKWXZ-sHp-3I8w_-vPyv4Oa4</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Globally optimal classification and pairing of human chromosomes</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Xiaolin Wu ; Biyani, P. ; Dumitrescu, S. ; Qiang Wu</creator><creatorcontrib>Xiaolin Wu ; Biyani, P. ; Dumitrescu, S. ; Qiang Wu</creatorcontrib><description>We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in polynomial time. In addition, we propose a technique of homologue pairing via maximum-weight graph matching. It obtains the globally optimal solution by forming all homologue pairs simultaneously under a maximum likelihood criterion, rather than finding one pair at a time as in existing heuristic algorithms. After the optimal homologue pairing, chromosome classification can also be done by maximum-weight graph matching. This new graph theoretical approach to chromosome pairing and classification is more robust than the transportation algorithm, because many attributes of a chromosome have less variations within a cell than between different cells.</description><identifier>ISBN: 0780384393</identifier><identifier>ISBN: 9780780384392</identifier><identifier>DOI: 10.1109/IEMBS.2004.1403797</identifier><language>eng</language><publisher>IEEE</publisher><subject>Biological cells ; Cells (biology) ; Classification algorithms ; Genetics ; Heuristic algorithms ; Humans ; Neural networks ; Polynomials ; Robustness ; Transportation</subject><ispartof>The 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 2004, Vol.1, p.2789-2792</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1403797$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,778,782,787,788,2054,4038,4039,27908,54903</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1403797$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Xiaolin Wu</creatorcontrib><creatorcontrib>Biyani, P.</creatorcontrib><creatorcontrib>Dumitrescu, S.</creatorcontrib><creatorcontrib>Qiang Wu</creatorcontrib><title>Globally optimal classification and pairing of human chromosomes</title><title>The 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society</title><addtitle>IEMBS</addtitle><description>We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in polynomial time. In addition, we propose a technique of homologue pairing via maximum-weight graph matching. It obtains the globally optimal solution by forming all homologue pairs simultaneously under a maximum likelihood criterion, rather than finding one pair at a time as in existing heuristic algorithms. After the optimal homologue pairing, chromosome classification can also be done by maximum-weight graph matching. This new graph theoretical approach to chromosome pairing and classification is more robust than the transportation algorithm, because many attributes of a chromosome have less variations within a cell than between different cells.</description><subject>Biological cells</subject><subject>Cells (biology)</subject><subject>Classification algorithms</subject><subject>Genetics</subject><subject>Heuristic algorithms</subject><subject>Humans</subject><subject>Neural networks</subject><subject>Polynomials</subject><subject>Robustness</subject><subject>Transportation</subject><isbn>0780384393</isbn><isbn>9780780384392</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2004</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNp9jrsKwjAYhQMieOsL6JIXsP4xhTabKPUydNK9_NbURnIpSR369nbo7FkOHwc-DiFrBjFjIHa3vDje4z1AErMEeCrSCVlAmgHPEi74jEQhfGAIFwNnc3K4aPdErXvq2k4Z1LTSGIKqVYWdcpaifdEWlVf2TV1Nm69BS6vGO-OCMzKsyLRGHWQ09pJszvnjdN0qKWXZ-sHp-3I8w_-vPyv4Oa4</recordid><startdate>2004</startdate><enddate>2004</enddate><creator>Xiaolin Wu</creator><creator>Biyani, P.</creator><creator>Dumitrescu, S.</creator><creator>Qiang Wu</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>2004</creationdate><title>Globally optimal classification and pairing of human chromosomes</title><author>Xiaolin Wu ; Biyani, P. ; Dumitrescu, S. ; Qiang Wu</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-ieee_primary_14037973</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2004</creationdate><topic>Biological cells</topic><topic>Cells (biology)</topic><topic>Classification algorithms</topic><topic>Genetics</topic><topic>Heuristic algorithms</topic><topic>Humans</topic><topic>Neural networks</topic><topic>Polynomials</topic><topic>Robustness</topic><topic>Transportation</topic><toplevel>online_resources</toplevel><creatorcontrib>Xiaolin Wu</creatorcontrib><creatorcontrib>Biyani, P.</creatorcontrib><creatorcontrib>Dumitrescu, S.</creatorcontrib><creatorcontrib>Qiang Wu</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Xiaolin Wu</au><au>Biyani, P.</au><au>Dumitrescu, S.</au><au>Qiang Wu</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Globally optimal classification and pairing of human chromosomes</atitle><btitle>The 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society</btitle><stitle>IEMBS</stitle><date>2004</date><risdate>2004</risdate><volume>1</volume><spage>2789</spage><epage>2792</epage><pages>2789-2792</pages><isbn>0780384393</isbn><isbn>9780780384392</isbn><abstract>We investigate globally optimal algorithms for automated classification and pairing of human chromosomes. Even in cases where the cell data are incomplete as often encountered in practice, we can still formulate the problem as a transportation problem, and hence find the globally optimal solution in polynomial time. In addition, we propose a technique of homologue pairing via maximum-weight graph matching. It obtains the globally optimal solution by forming all homologue pairs simultaneously under a maximum likelihood criterion, rather than finding one pair at a time as in existing heuristic algorithms. After the optimal homologue pairing, chromosome classification can also be done by maximum-weight graph matching. This new graph theoretical approach to chromosome pairing and classification is more robust than the transportation algorithm, because many attributes of a chromosome have less variations within a cell than between different cells.</abstract><pub>IEEE</pub><doi>10.1109/IEMBS.2004.1403797</doi></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0780384393
ispartof The 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 2004, Vol.1, p.2789-2792
issn
language eng
recordid cdi_ieee_primary_1403797
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Biological cells
Cells (biology)
Classification algorithms
Genetics
Heuristic algorithms
Humans
Neural networks
Polynomials
Robustness
Transportation
title Globally optimal classification and pairing of human chromosomes
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-16T20%3A52%3A56IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Globally%20optimal%20classification%20and%20pairing%20of%20human%20chromosomes&rft.btitle=The%2026th%20Annual%20International%20Conference%20of%20the%20IEEE%20Engineering%20in%20Medicine%20and%20Biology%20Society&rft.au=Xiaolin%20Wu&rft.date=2004&rft.volume=1&rft.spage=2789&rft.epage=2792&rft.pages=2789-2792&rft.isbn=0780384393&rft.isbn_list=9780780384392&rft_id=info:doi/10.1109/IEMBS.2004.1403797&rft_dat=%3Cieee_6IE%3E1403797%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-ieee_primary_14037973%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1403797&rfr_iscdi=true