利用计算机程序寻找匹配肾源

A man in St. Louis and a woman in New Hampshire have received the first kidney transplants made possible through a new national program of the Organ Procurement¹（采购，获得） and Transplantation Network (OPTN) that uses a Carnegie Mellon University computer algorithm（计算机程序法） to match transplant candidates with living donors². Both recipients⁴ — Ken⁵ Crowder of St. Louis and Kathy Niedzwiecki of Pelham, N.H. — had loved ones who were willing to donate a kidney but who were medically incompatible⁶（不相容的） with them. So, through a paired donation, Mr. Crowder's fiancée, Rebecca Burkes, donated her kidney to Ms. Niedzwiecki and Ms. Niedzwiecki's sister-in-law, Cathy Richard of Henniker, N.H., donated her kidney to Mr. Crowder. The donor³ recovery and transplant operations took place Dec. 6 at Barnes-Jewish Hospital in St. Louis and Dartmouth-Hitchcock Medical Center in Lebanon, N.H.

The matches were identified during a computer run Oct. 27 that considered 43 transplant candidates and 45 donors. It was the first match run of the OPTN pilot program（试点工程） , which is expected to increase the number of kidney paired-donation (KPD) transplants by creating a national pool of mismatched donor-recipient pairs. The United Network for Organ Sharing (UNOS) operates the OPTN under federal contract.

"It is gratifying（令人满足的） to know that this pilot program has helped make these transplants possible," said Tuomas Sandholm, a professor of computer science at Carnegie Mellon who has led the development of computer algorithms for optimizing⁷ match runs. "As the size of the pool increases, we are confident that we can significantly boost the number of patients who are able to receive kidney transplants. The more people in the pool, the higher the portion of them we can save."

"Paired donation is helping⁸ the transplant community help people who otherwise could not get a living donor transplant. We're proud to be able to coordinate⁹ these for the first time using a national network for potential matches among 77 participating transplant programs," said Charles Alexander, OPTN/UNOS president.

Alexander said the Carnegie Mellon algorithm and Sandholm's expert advice were important parts of the pilot program. "These contributions have helped us develop the program more quickly and at significantly lower cost than we could have achieved otherwise, so we can focus on saving and enhancing lives through kidney paired-donation," he explained.

Smaller, existing kidney exchanges, which take these incompatible donor-recipient pairs and match them with other donor-recipient pairs, already have increased the number of KPD transplants. In the last three years, exchanges have enabled more than 700 kidney transplants that otherwise would not have occurred. Two of those exchanges have used the Carnegie Mellon computer algorithm to match pairs.

"The goal of the pilot project is to see whether combining the data of multiple centers and networks will generate successful matches that may not be found through one individual organization," Alexander said. "The fact that these transplants occurred from the first match run suggests this will be true."

Examining all of the possible combinations of two- and three-way exchanges between the donor-recipient pairs is a massive computational task. The first algorithm that could solve this problem optimally¹⁰ on a nationwide scale — a projected 10,000 pairs in the pool — was developed in 2006 by Sandholm, Computer Science Professor Avrim Blum and then-graduate student David J. Abraham. The algorithm has since been further refined by Sandholm and Ph.D. students Pranjal Awasthi, Erik Zawadzki and John Dickerson.

The optimization¹² problem places a huge demand on computer memory, Sandholm said. Therefore, the algorithm never writes down the entire problem in the computer's memory. It nevertheless finds an optimal¹¹ solution by formulating¹³ into memory only those parts of the problem that turn out to be relevant.

Future match runs will be conducted every four to five weeks with information on potential living donors and candidates supplied by pilot participants. Each transplant program will make individual medical decisions about accepting living donors or candidates and whether they qualify for matching through the pilot program. In addition, each program must document that potential living donors have undergone a rigorous（严格的，严厉的） medical screening and have provided detailed¹⁴ informed consent（同意，赞成） for donation and for potential participation¹⁵ in a national match run.

The need to increase the efficiency of kidney exchanges is compelling. The demand for donor organs — more than 86,000 people are now on the kidney waiting list — far exceeds supply. Last year, 28,463 people received kidney transplants, with 6,609 of those kidneys coming from living donors.